MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers

• URL: http://arxiv.org/abs/2205.14210v1
• Date: Fri, 27 May 2022 19:34:14 GMT
• Title: MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers
• Authors: Elias B. Khalil, Christopher Morris, Andrea Lodi
• Abstract summary: Mixed-integer programming (MIP) technology offers a generic way of formulating and solving optimization problems. MIP-GNN is a general framework for enhancing such solvers with data-driven insights. We integrate MIP-GNN into a state-of-the-art MIP solver, applying it to tasks such as node selection and warm-starting.
• Score: 13.790116387956703
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mixed-integer programming (MIP) technology offers a generic way of formulating and solving combinatorial optimization problems. While generally reliable, state-of-the-art MIP solvers base many crucial decisions on hand-crafted heuristics, largely ignoring common patterns within a given instance distribution of the problem of interest. Here, we propose MIP-GNN, a general framework for enhancing such solvers with data-driven insights. By encoding the variable-constraint interactions of a given mixed-integer linear program (MILP) as a bipartite graph, we leverage state-of-the-art graph neural network architectures to predict variable biases, i.e., component-wise averages of (near) optimal solutions, indicating how likely a variable will be set to 0 or 1 in (near) optimal solutions of binary MILPs. In turn, the predicted biases stemming from a single, once-trained model are used to guide the solver, replacing heuristic components. We integrate MIP-GNN into a state-of-the-art MIP solver, applying it to tasks such as node selection and warm-starting, showing significant improvements compared to the default setting of the solver on two classes of challenging binary MILPs.

Related papers

• Deep learning enhanced mixed integer optimization: Learning to reduce model dimensionality [0.0]
  This work introduces a framework to address the computational complexity inherent in Mixed-Integer Programming. By employing deep learning, we construct problem-specific models that identify and exploit common structures across MIP instances. We present an algorithm for generating synthetic data enhancing the robustness and generalizability of our models.
  arXiv  Detail & Related papers  (2024-01-17T19:15:13Z)
• An Expandable Machine Learning-Optimization Framework to Sequential Decision-Making [0.0]
  We present an integrated prediction-optimization (PredOpt) framework to efficiently solve sequential decision-making problems. We address the key issues of sequential dependence, infeasibility, and generalization in machine learning (ML) to make predictions for optimal solutions to instances problems.
  arXiv  Detail & Related papers  (2023-11-12T21:54:53Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  We introduce the first-ever completely equivariant model and training to solve problems. It is essential to capture the multiscale structure of the input graph. We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
  arXiv  Detail & Related papers  (2023-10-24T06:22:20Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  We propose a multi-head ensemble multi-task learning (MEMTL) approach with a shared backbone and multiple prediction heads (PHs) MEMTL outperforms benchmark methods in both the inference accuracy and mean square error without requiring additional training data.
  arXiv  Detail & Related papers  (2023-09-02T11:01:16Z)
• Solving Recurrent MIPs with Semi-supervised Graph Neural Networks [15.54959083707859]
  We propose an ML-based model that automates and expedites the solution of MIPs by predicting the values of variables. Our approach is motivated by the observation that many problem instances share salient features and solution structures. Examples include transportation and routing problems where decisions need to be re-optimized whenever commodity volumes or link costs change.
  arXiv  Detail & Related papers  (2023-02-20T15:57:56Z)
• A Survey for Solving Mixed Integer Programming via Machine Learning [76.04988886859871]
  This paper surveys the trend of machine learning to solve mixed integer (MIP) problems. In this paper, we first introduce the formulation and preliminaries of MIP and several traditional algorithms to solve MIP. Then, we advocate further promoting the different integration of machine learning and MIP algorithms.
  arXiv  Detail & Related papers  (2022-03-06T05:03:37Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed. An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed. We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
  arXiv  Detail & Related papers  (2020-06-15T02:57:57Z)
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks [2.7473982588529653]
  We study the problem of learning the sparse DAG structure of a BN from continuous observational data. The optimal solution to this mathematical program is known to have desirable statistical properties under certain conditions. We propose a concrete early stopping criterion to terminate the branch-and-bound process in order to obtain a near-optimal solution.
  arXiv  Detail & Related papers  (2020-05-29T00:13:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.