Metraipolis › archive › dc_cd45b6d5ba9f

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.30103
License (as archived)
CC0-1.0
Archived
2026-10-17T07:52:24.907Z
SHA-256 of the archived text
57f371c95e80d8809d08495e0d3ee1bb6815c2a0a4852dc22783c0f2d9db3b9f
Stable URL of this page
https://metraipolis.com/documento/dc_cd45b6d5ba9f

How to cite

Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization — arXiv:2608.30103 — arXiv (en), https://arxiv.org/abs/2608.30103 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd45b6d5ba9f (Metraipolis archive dc_cd45b6d5ba9f, sha256 57f371c95e80d8809d08495e0d3ee1bb6815c2a0a4852dc22783c0f2d9db3b9f)
BibTeX
@misc{dccd45b6d5ba9f,
  title = {Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization — arXiv:2608.30103},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.30103},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd45b6d5ba9f; sha256 57f371c95e80d8809d08495e0d3ee1bb6815c2a0a4852dc22783c0f2d9db3b9f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.30103. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-01 in cs.AI).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2608.30103 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T07:28:26.825Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).