PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization

Jessica D. Elrefaei, Kaixun Hua, Seungbae Kim, Hoang Nam Tran, Juan S. Borrero

arXiv:2608.30103v1cs.LGcs.AI

TL;DR

BMILPs require optimizing a leader’s decision while anticipating a follower’s optimal response, making exact value-function evaluation costly. Graph4BiLO learns that value function from variable–constraint graphs with shared message-passing parameters, embeds the ReLU surrogate in a mixed-integer formulation, and repairs the follower response exactly. On knapsack interdiction, it achieves objective values comparable to Neur2BiLO across tested sizes while exposing a scalability tradeoff from costly GNN embeddings.

  • Problem

    BMILPs are difficult because lower-level optimality is embedded in the leader’s feasible region and exact value-function evaluation can require solving discrete optimization problems repeatedly.

  • Method

    Graph4BiLO learns follower value functions from variable–constraint graphs using shared GNN parameters, encodes the trained ReLU network as mixed-integer constraints, and exactly re-solves the follower problem for repair.

  • Results

    Graph4BiLO produces objective values comparable to Neur2BiLO on 20–100-item knapsack interdiction instances while using one model across multiple problem sizes.

  • Takeaways & Limitations

    Shared graph parameters support applying one trained model across variable-sized optimization instances and enable cross-size reuse of training and fitting effort.

  • Takeaways & Limitations

    Node-wise ReLU embeddings enlarge the mixed-integer formulation and make optimization difficult for larger instances, while deeper message passing does not monotonically improve prediction.

Abstract

from arXiv · show

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.

I. INTRODUCTION

BMILPs capture hierarchical decisions but are difficult because follower optimality is nested within the leader’s problem. Graph4BiLO learns value functions with graph-based shared parameters, embeds the surrogate in optimization, and evaluates size-generalization and computational tradeoffs.

  • BMILPs model leaders anticipating optimal follower responses, but nested lower-level optimality makes them harder than single-level mixed-integer programs.
  • Exact value-function evaluation can require solving a mixed-integer problem for each leader decision considered during optimization.
  • Unlike reported size-specific Neur2BiLO experiments, Graph4BiLO evaluates one model across sizes, including zero-shot transfer to unseen instances.
  • Graph4BiLO represents bilevel instances as variable–constraint graphs and uses a GNN surrogate with shared parameters across problem sizes.
  • The framework embeds the trained ReLU GNN in a mixed-integer approximation and repairs the selected solution by re-solving the follower problem.
  • The study compares Graph4BiLO with exact and learning-based baselines while quantifying tradeoffs involving GNN depth and global information sharing.

B. Value-Function Reformulation

The value-function reformulation replaces the nested follower optimization with a constraint involving the follower’s optimal value. This removes the explicit nested structure but leaves value-function evaluation computationally difficult.

  • The follower value function returns the follower’s optimal objective value for a fixed leader decision.
  • Follower feasibility together with a value-function optimality constraint forces the follower solution to attain its optimal value.
  • Value-function reformulation produces a single-level model in form, but exact evaluation can still require solving a difficult discrete optimization problem.

A. Overview

Graph4BiLO learns follower value functions from graph representations of bilevel instances and embeds the learned network into an approximate single-level model. Its graph construction preserves algebraic interactions among leader variables, follower variables, and constraints.

  • Graph4BiLO generates sampled leader decisions, solves each follower problem exactly, and trains a GNN on graph–value pairs.
  • After training, the fixed ReLU network is encoded as mixed-integer constraints, embedded in an approximate formulation, and followed by an exact follower re-solve.
  • In knapsack interdiction, the leader interdicts items while the follower packs remaining items to maximize profit, so the leader minimizes the follower’s optimal profit.
  • Variable–Constraint Graph Construction: The graph contains follower-variable, leader-variable, and constraint nodes constructed from nonzero entries of matrices F and L.
  • Variable–Constraint Graph Construction: Matrix-induced edges carry coefficient weights, while shortcut edges directly connect leader and follower variables appearing in the same constraint row.
  • Variable–Constraint Graph Construction: An n-item knapsack interdiction instance has 3n + 1 graph nodes: n follower nodes, n leader nodes, and n + 1 constraint nodes.

D. Heterogeneous GNN Architecture

Graph4BiLO uses a heterogeneous GNN to encode leader variables, follower variables, and constraints through relation-specific message passing, global context, and pooling. Shared parameters and fixed-dimensional readout enable application across varying problem sizes.

  • D. Heterogeneous GNN Architecture: Type-specific node projections map heterogeneous features into a common hidden space before relation-specific message passing updates each node type.Messages are summed by destination type and passed through ReLU transformations.
  • D. Heterogeneous GNN Architecture: Graph4BiLO represents leader-variable, follower-variable, and constraint nodes in a heterogeneous graph with six directed relation types.Separate transformations are learned for each semantic relation, including y→c, c→y, x→c, c→x, x→y, and y→x.
  • D. Heterogeneous GNN Architecture: Global pooling and broadcast supply every node with graph-level context beyond its local message-passing receptive field.Mean pooling is performed separately over follower-variable, leader-variable, and constraint nodes before the summary is broadcast back through type-specific transformations.
  • D. Heterogeneous GNN Architecture: A second type-wise mean-pooling step converts variable-sized node collections into a fixed-dimensional graph representation for readout.The final readout dimensionality therefore does not depend on the number of items in the instance.
  • D. Heterogeneous GNN Architecture: Reference features and a linear readout produce the learned lower-level value-function approximation ϕG(x; θ).The reference features include the no-interdiction follower objective and an additional 1.25×K objective feature.
  • D. Heterogeneous GNN Architecture: Shared relation parameters do not depend on node count, allowing one trained Graph4BiLO model to operate on graphs with different numbers of variables and constraints.This provides the architectural basis for cross-size application.

E. Training Objective

Graph4BiLO trains its value-function predictor against exact lower-level objective values using the Huber loss. This loss preserves sensitivity to small errors while reducing the influence of large residuals.

  • E. Training Objective: The training objective is defined from the supervised value-function prediction errors.The supplied training-objective passages introduce the supervised set and objective formulation.
  • E. Training Objective: The model is trained by minimizing the Huber loss between predicted and exact lower-level objective values.
  • E. Training Objective: The Huber loss is quadratic for small prediction errors and linear for larger errors.Compared with mean squared error, this reduces the influence of large residuals while encouraging accurate prediction.

A. Mixed-Integer ReLU Encoding

The trained ReLU value-function network is encoded exactly with mixed-integer linear constraints and embedded in an approximate single-level bilevel formulation. A slack-penalized surrogate solution is then repaired by resolving the original follower problem.

  • A. Mixed-Integer ReLU Encoding: Valid pre-activation bounds allow each ReLU neuron to be represented exactly with mixed-integer linear constraints.A binary activation indicator encodes the neuron’s active or inactive state.
  • A. Mixed-Integer ReLU Encoding: Graph4BiLO replaces the exact follower value with the learned approximation in the single-level model.For knapsack interdiction, the approximate formulation uses binary leader and follower variables.
  • A. Mixed-Integer ReLU Encoding: A nonnegative slack variable protects against infeasibility from value-function overprediction, while λ penalizes the relaxation.The trained parameters remain fixed during optimization.
  • A. Mixed-Integer ReLU Encoding: The approximate model returns a candidate leader–follower pair, after which the original follower problem is re-solved with the leader decision fixed.This repair step obtains the exact follower response for the selected leader decision.
  • A. Mixed-Integer ReLU Encoding: Replacing the approximate follower decision with the repaired response restores lower-level optimality, which the optimality residual verifies.

V. COMPUTATIONAL EXPERIMENTS

Computational experiments compare Graph4BiLO with MibS and Neur2BiLO on knapsack interdiction across problem sizes, including zero-shot tests on unseen sizes. Graph4BiLO achieves comparable objectives and cross-size transfer, but its embedded GNN causes much higher solve times.

  • V. COMPUTATIONAL EXPERIMENTS: The study evaluates 10,000 generated instances across n ∈ {20, 40, 60, 80, 100}, with exact follower values and stratified train, validation, and test splits.Each size contributes 2,000 instances.
  • V. COMPUTATIONAL EXPERIMENTS: Graph4BiLO, MibS, and Neur2BiLO are evaluated on the same 10 test instances per problem size under a 3,600-second maximum time limit.
  • V. COMPUTATIONAL EXPERIMENTS: Graph4BiLO achieves mean objective values close to Neur2BiLO across all tested sizes, while both learning-based methods outperform MibS from n = 40 onward within the time limit.At n = 20, Graph4BiLO’s mean objective is 0.58, versus 0.55 for MibS and 0.54 for Neur2BiLO.
  • V. COMPUTATIONAL EXPERIMENTS: 29.52 seconds at n = 20 and 1049.44 seconds at n = 40 are Graph4BiLO’s reported average solve times, reaching the one-hour limit for n ≥60.Neur2BiLO solves the approximate optimization problem in approximately 0.1 seconds on average.
  • V. COMPUTATIONAL EXPERIMENTS: One trained graph-based model can be applied to instances with different numbers of variables and constraints.This cross-size capability is a principal advantage of the representation.
  • V. COMPUTATIONAL EXPERIMENTS: At n = 40, zero-shot Graph4BiLO trained only on n = 20 obtains mean objective 0.978 in 2.92 seconds, while MibS reaches 3,600 seconds with objective 1.895.The model is evaluated without retraining or fine-tuning.
  • V. COMPUTATIONAL EXPERIMENTS: Using one n = 20 model requires 2,000 labeled lower-level solves instead of 6,000 for separate n = 20, 40, and 60 models.The comparison also involves one training procedure rather than three.
  • V. COMPUTATIONAL EXPERIMENTS: At n = 60, zero-shot Graph4BiLO obtains mean objective 1.609 in 5.81 seconds, while MibS reaches 3,600 seconds with objective 3.489.The model remains effective when test size triples from the n = 20 training instances.

D. Architecture Ablation

The ablation shows that deeper message passing does not reliably improve prediction or optimization outcomes, while increasing the embedded formulation’s computational burden. Global broadcast improves representation and solution quality but makes the formulation harder to solve.

  • Predictive accuracy: Two-layer message passing achieves the lowest Huber loss, MAE, and RMSE, while deeper models do not improve predictive accuracy.The study reports no monotonic accuracy improvement as depth increases.
  • Optimization performance: The one-layer model attains the lowest mean leader objective, 0.5395, despite the two-layer model having the lowest prediction errors.The four-layer model follows with a mean leader objective of 0.5767.
  • Global broadcast: Removing global broadcast reduces mean solve time from 3.49 to 1.42 seconds but increases Huber loss from 0.010679 to 0.014493.The same removal increases MAE from 0.118443 to 0.130136 and mean leader objective from 0.5767 to 0.7060.
  • Overall tradeoff: Increasing depth beyond two layers adds ReLU variables, constraints, and bound-propagation work without clear predictive benefit for this benchmark.The resulting tradeoff includes increased optimization complexity and possible representation homogenization.
  • Embedded formulation size: At n = 100, the main d = 32, L = 2 architecture can introduce approximately 28,896 binary and 57,792 continuous variables.These variables arise from node-wise ReLU representations and their mixed-integer encoding.

F. Tradeoff Between Receptive Coverage and GNN Depth

Local message passing expands receptive coverage with depth, but deeper embedded GNNs can homogenize node representations and enlarge the optimization model. Global broadcast supplies instance-wide information without additional local layers, while introducing its own tension with local distinctness.

  • Receptive coverage: Four local message-passing layers are sufficient, and sometimes necessary, for arbitrary nodes to exchange information in the graph.The knapsack-interdiction graph has diameter four, making layer four the depth for complete local receptive coverage.
  • Depth tradeoff: Deeper networks increase representational reach but also homogenize node states and add node-wise ReLU constraints to the embedded model.These competing effects are central to using local message-passing GNNs inside optimization models.
  • Representation similarity: At layer four, mean within-type cosine similarity reaches 0.947 for follower variables, 0.970 for constraints, and 0.986 for leader variables.These values indicate highly similar representations at the depth required for full local coverage.
  • Global information: Global broadcast increases those similarities to 0.985, 1.000, and 0.997 for follower variables, constraints, and leader variables, respectively.Broadcast gives every node the same graph-level summary, providing global context without extra local layers.
  • Optimization cost: 0.28 seconds is the one-layer solve time, versus 3.20, 4.30, and 3.49 seconds for two-, three-, and four-layer models.The comparison uses n = 20 instances with hidden dimension d = 4.
  • Design implication: Graph4BiLO balances local structural reasoning, global information access, and the computational cost of deeper embedded networks.Its two local layers are followed by global pooling and broadcast rather than full local graph traversal.

VI. DISCUSSION

Graph4BiLO offers cross-size reuse through shared graph parameters, but this flexibility comes with larger embedded MILPs and higher computational cost. The discussion frames model choice as a tradeoff between portability, label-generation cost, predictive quality, and optimization efficiency.

  • Practical Guidance: For a fixed problem size, Neur2BiLO achieves essentially the same objective quality while producing a much smaller and faster embedded optimization model.The discussion therefore presents the compact surrogate as attractive when optimization repeatedly occurs at one fixed dimension.
  • Practical Guidance: Graph4BiLO becomes attractive when one model must serve multiple problem sizes, including zero-shot transfer from n = 20 to n = 40 and n = 60 without retraining.Supporting n = 20, 40, and 60 with size-specific models would require 6,000 lower-level solves and three training procedures, whereas the OOD experiment uses 2,000 labeled n = 20 instances and one model.
  • Practical Guidance: Graph4BiLO exchanges structural parameter sharing and cross-size transfer for a substantially larger embedded MILP.This tradeoff is not limited to predictive accuracy versus computational efficiency; it also reflects whether changing dimensions and expensive label generation matter operationally.
  • Limitations and Future Directions: The evaluation is limited to knapsack interdiction, and the cross-size experiment does not establish superiority over every variable-size neural architecture.The authors identify matched cross-size comparisons and other bilevel problem classes as important future directions.
  • Limitations and Future Directions: Embedding the GNN directly in the optimization model is the principal scalability limitation because node-wise ReLU activations add variables and constraints as graph size, hidden dimension, and depth increase.The resulting formulation becomes difficult to solve for larger instances.
  • Limitations and Future Directions: Increasing message-passing depth does not monotonically improve prediction quality, and four-hop representations show substantial homogenization.The discussion motivates future work on reducing or redesigning the mixed-integer representation of the GNN.
Loading 2608.30103v1…