A Max-Cut-specific graph neural network predicts primal- and dual-feasible SDP solutions in linearithmic time, cutting bounding costs in exact branch-and-bound by up to 10.6 times versus a commercial SDP solver while training without any solved SDP labels.
hub
Solving mixed integer programs using neural networks
13 Pith papers cite this work. Polarity classification is still indexing.
13
Pith papers citing it
abstract
Mixed Integer Programming (MIP) solvers rely on an array of sophisticated heuristics developed with decades of research to solve large-scale MIP instances encountered in practice. Machine learning offers to automatically construct better heuristics from data by exploiting shared structure among instances in the data. This paper applies learning to the two key sub-tasks of a MIP solver, generating a high-quality joint variable assignment, and bounding the gap in objective value between that assignment and an optimal one. Our approach constructs two corresponding neural network-based components, Neural Diving and Neural Branching, to use in a base MIP solver such as SCIP. Neural Diving learns a deep neural network to generate multiple partial assignments for its integer variables, and the resulting smaller MIPs for un-assigned variables are solved with SCIP to construct high quality joint assignments. Neural Branching learns a deep neural network to make variable selection decisions in branch-and-bound to bound the objective value gap with a small tree. This is done by imitating a new variant of Full Strong Branching we propose that scales to large instances using GPUs. We evaluate our approach on six diverse real-world datasets, including two Google production datasets and MIPLIB, by training separate neural networks on each. Most instances in all the datasets combined have $10^3-10^6$ variables and constraints after presolve, which is significantly larger than previous learning approaches. Comparing solvers with respect to primal-dual gap averaged over a held-out set of instances, the learning-augmented SCIP is 2x to 10x better on all datasets except one on which it is $10^5$x better, at large time limits. To the best of our knowledge, ours is the first learning approach to demonstrate such large improvements over SCIP on both large-scale real-world application datasets and MIPLIB.
hub tools
representative citing papers
GraphBU generates MILP instances via graph-native block units that pair local subproblems with explicit coupling interfaces, achieving high structural similarity and feasibility preservation across four MILP families.
A parallel tempering sampling method with locally-balanced proposals and penalty tempering solves ILP problems competitively with SCIP and Gurobi while showing robustness to distribution shift.
LLM4Branch discovers branching policies for MILP solvers as LLM-generated executable programs whose parameters are tuned via zeroth-order optimization on solver performance.
InvEvolve evolves inventory policies using LLMs with RL and provides statistical safety guarantees, outperforming classical and DL methods on synthetic and real data.
A hybrid RL and self-supervised learning method accelerates generalized Benders decomposition by 57.5% on a MINLP case study while recovering optimal solutions.
Local d-hop uniqueness in GNN node features matches global UID expressiveness for ILP solving while providing stronger generalization.
Classical solver KaMIS outperforms leading AI methods for Maximum Independent Set on random graphs, with some AI approaches no better than simple greedy heuristics and a new serialization analysis revealing similar reasoning.
Multipartite GNN learns MILP formulations of network interdiction to outperform baselines on bi-level combinatorial tasks.
A DRO model integrated with generative AI for robust capacity planning in green manufacturing under demand and renewable uncertainty.
Feasibility-aware imitation learning accelerates Benders decomposition by predicting feasible integer assignments in the master problem, improving solution times over prior imitation learning methods while retaining finite convergence.
RL-SPH is an RL-based start primal heuristic that learns to turn infeasible starting points into feasible integer linear programming solutions, including problems with non-binary integers.
citing papers explorer
-
Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
A Max-Cut-specific graph neural network predicts primal- and dual-feasible SDP solutions in linearithmic time, cutting bounding costs in exact branch-and-bound by up to 10.6 times versus a commercial SDP solver while training without any solved SDP labels.
-
GraphBU: MILP Instance Generation with Graph-Native Block Units
GraphBU generates MILP instances via graph-native block units that pair local subproblems with explicit coupling interfaces, achieving high structural similarity and feasibility preservation across four MILP families.
-
Solving Integer Linear Programming with Parallel Tempering
A parallel tempering sampling method with locally-balanced proposals and penalty tempering solves ILP problems competitively with SCIP and Gurobi while showing robustness to distribution shift.
-
LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs
LLM4Branch discovers branching policies for MILP solvers as LLM-generated executable programs whose parameters are tuned via zeroth-order optimization on solver performance.
-
InvEvolve: Evolving White-Box Inventory Policies via Large Language Models with Performance Guarantees
InvEvolve evolves inventory policies using LLMs with RL and provides statistical safety guarantees, outperforming classical and DL methods on synthetic and real data.
-
A Hybrid Reinforcement and Self-Supervised Learning Aided Benders Decomposition Algorithm
A hybrid RL and self-supervised learning method accelerates generalized Benders decomposition by 57.5% on a MINLP case study while recovering optimal solutions.
-
Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices
Local d-hop uniqueness in GNN node features matches global UID expressiveness for ILP solving while providing stronger generalization.
-
Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set
Classical solver KaMIS outperforms leading AI methods for Maximum Independent Set on random graphs, with some AI approaches no better than simple greedy heuristics and a new serialization analysis revealing similar reasoning.
-
Network Interdiction Goes Neural
Multipartite GNN learns MILP formulations of network interdiction to outperform baselines on bi-level combinatorial tasks.
-
Green Manufacturing Capacity Planning by Integrating Distributionally Robust Optimization and Generative AI
A DRO model integrated with generative AI for robust capacity planning in green manufacturing under demand and renewable uncertainty.
-
Feasibility-Aware Imitation Learning for Benders Decomposition
Feasibility-aware imitation learning accelerates Benders decomposition by predicting feasible integer assignments in the master problem, improving solution times over prior imitation learning methods while retaining finite convergence.
-
RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs
RL-SPH is an RL-based start primal heuristic that learns to turn infeasible starting points into feasible integer linear programming solutions, including problems with non-binary integers.
- GRIMIP: A General Framework for Instance-Specific Configuration of MIP Solvers Using LLMs