On Representing Mixed-Integer Linear Programs by Graph Neural Networks
While Mixed-integer linear programming (MILP) is NP-hard in general, practical MILP has received roughly 100--fold speedup in the past twenty years. Still, many classes of MILPs quickly become unsolvable as their sizes increase, motivating researchers to seek new acceleration techniques for MILPs. With deep learning, they have obtained strong empirical results, and many results were obtained by applying graph neural networks (GNNs) to making decisions in various stages of MILP solution processes. This work discovers a fundamental limitation: there exist feasible and infeasible MILPs that all GNNs will, however, treat equally, indicating GNN's lacking power to express general MILPs. Then, we show that, by restricting the MILPs to unfoldable ones or by adding random features, there exist GNNs that can reliably predict MILP feasibility, optimal objective values, and optimal solutions up to prescribed precision. We conducted small-scale numerical experiments to validate our theoretical findings.
Code (1)
Similar Papers 제목 키워드 기반
A mixed-integer framework for analyzing neural network-based controllers for piecewise affine systems with bounded disturbances
We present a method for representing the closed-loop dynamics of piecewise affine (PWA) systems with bounded additive disturbances and neural network-based controllers as mixed-integer (MI) linear constraints. We show th…
Learning for Online Mixed-Integer Model Predictive Control with Parametric Optimality Certificates
We propose a supervised learning framework for computing solutions of multi-parametric Mixed Integer Linear Programs (MILPs) that arise in Model Predictive Control. Our approach also quantifies sub-optimality for the com…
Model Predictive ControlMotion PlanningReLU Networks as Surrogate Models in Mixed-Integer Linear Programs
We consider the embedding of piecewise-linear deep neural networks (ReLU networks) as surrogate models in mixed-integer linear programming (MILP) problems. A MILP formulation of ReLU networks has recently been applied by…
Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning
Many real-world problems can be efficiently modeled as Mixed Integer Linear Programs (MILPs) and solved with the Branch-and-Bound method. Prior work has shown the existence of MILP backdoors, small sets of variables such…
Contrastive LearningGraph AttentionPredicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs
Lagrangian relaxation stands among the most efficient approaches for solving a Mixed Integer Linear Programs (MILP) with difficult constraints. Given any duals for these constraints, called Lagrangian Multipliers (LMs), …
Decoder