analiza aiqbench
Graph4BiLO applies graph neural networks to approximate value functions in bilevel mixed-integer linear optimization, enabling a single model to generalize across varying problem sizes without retraining. By encoding the learned ReLU network as mixed-integer constraints, the method balances approximation accuracy with computational feasibility, though it highlights a tradeoff between representation size and solve time for large-scale instances. This research advances the intersection of graph learning and combinatorial optimization, offering a scalable approach to hierarchical decision-making problems.
Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization
arXiv:2608.30103v1 Announce Type: cross 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.
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.
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2608.30103 [cs.LG]
(or arXiv:2608.30103v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2608.30103 arXiv-issued DOI via DataCite (pending registration)
Text integral sub licența deschisă a publicației · 285 cuvinte
Subiecte conexe
AI-Driven Multi-Hop Relay Selection for Smart Urban NR-V2X Networks via Learning-to-Optimize Graph Neural Networks
arXiv · 24 iul. 2026
DCEmbed: Scalable Optimization over Neural Surrogates
arXiv · 30 sept. 2026
Optimized Piecewise Affine Abstractions of Neural Networks with Learnable Activation Functions
arXiv · 5 aug. 2026
DisjunctiveNet: Neural Symbolic Learning via Differentiable Convexified Optimization Layers
arXiv · 4 aug. 2026