AI summaryⓘ
The authors study bilevel optimization problems where one decision-maker (the leader) must anticipate the best response of another (the follower). They propose Graph4BiLO, a method using graph neural networks (GNNs) to learn how the follower will behave across different problem sizes, unlike traditional methods that need separate models for each size. This learned model is embedded into the optimization problem to find good leader decisions, with a fix-up step ensuring follower feasibility. Their tests show Graph4BiLO matches other learning methods in solution quality and can handle bigger problems than it was trained on, but it does increase problem size and computation time. The authors highlight a tradeoff between using flexible graph models and the added cost of embedding them in the optimization process.
bilevel optimizationmixed-integer linear programmingleader-follower modelgraph neural networksvalue-function reformulationknapsack interdictionmessage passingzero-shot transferReLU networksapproximate single-level formulation
Authors
Jessica D. Elrefaei, Kaixun Hua, Seungbae Kim, Hoang Nam Tran, Juan S. Borrero
Abstract
Bilevel mixed-integer linear optimization problems model hierarchical decision processes in which a leader anticipates the optimal response of a follower. Although expressive, these problems are computationally challenging because lower-level optimality is embedded in the leader's feasible region. Value-function reformulations replace the nested follower optimization with a constraint involving the follower's optimal value, but evaluating this value function exactly can itself be expensive. This paper introduces Graph4BiLO, a graph neural network (GNN) approach for learning bilevel value functions from variable--constraint graph representations. In contrast to fixed-length multilayer perceptron (MLP) representations, the GNN uses shared message-passing parameters and can therefore be applied across multiple problem sizes with a single trained model. The learned ReLU network is encoded exactly as mixed-integer linear constraints and embedded in an approximate single-level formulation. A repair step subsequently re-solves the follower problem for the selected leader decision to recover a bilevel-feasible follower response. We evaluate Graph4BiLO on knapsack interdiction instances with 20--100 items against the exact MibS solver and the learning-based Neur2BiLO method. Graph4BiLO obtains objective values comparable to Neur2BiLO across all tested sizes while avoiding size-specific neural networks. An additional out-of-distribution experiment demonstrates zero-shot transfer from 20-item training instances to previously unseen 40- and 60-item instances. However, embedding message passing at every graph node substantially increases the resulting mixed-integer formulation size and solve time. These results identify a central tradeoff between size-generalizable graph representations and the computational cost of embedding GNNs within optimization models.