A Survey for Solving Mixed Integer Programming via Machine Learning

• URL: http://arxiv.org/abs/2203.02878v1
• Date: Sun, 6 Mar 2022 05:03:37 GMT
• Title: A Survey for Solving Mixed Integer Programming via Machine Learning
• Authors: Jiayi Zhang and Chang Liu and Junchi Yan and Xijun Li and Hui-Ling Zhen and Mingxuan Yuan
• Abstract summary: 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.
• Score: 76.04988886859871
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper surveys the trend of leveraging machine learning to solve mixed integer programming (MIP) problems. Theoretically, MIP is an NP-hard problem, and most of the combinatorial optimization (CO) problems can be formulated as the MIP. Like other CO problems, the human-designed heuristic algorithms for MIP rely on good initial solutions and cost a lot of computational resources. Therefore, we consider applying machine learning methods to solve MIP, since ML-enhanced approaches can provide the solution based on the typical patterns from the historical data. 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 and introducing related learning-based methods, which can be classified into exact algorithms and heuristic algorithms. Finally, we propose the outlook for learning-based MIP solvers, direction towards more combinatorial optimization problems beyond MIP, and also the mutual embrace of traditional solvers and machine learning components.

Related papers

• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS) For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. We extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.
  arXiv  Detail & Related papers  (2024-04-30T06:48:56Z)
• 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)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  We present a comprehensive study on the integration of machine learning (ML) techniques into Huawei Cloud's OptVerse AI solver. We showcase our methods for generating complex SAT and MILP instances utilizing generative models that mirror multifaceted structures of real-world problem. We detail the incorporation of state-of-the-art parameter tuning algorithms which markedly elevate solver performance.
  arXiv  Detail & Related papers  (2024-01-11T15:02:15Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. We introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. We show that our algorithm provides comparable sublinear regret to the existing works.
  arXiv  Detail & Related papers  (2023-10-10T01:39:04Z)
• A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization [2.9882027965916413]
  Influence Maximization (IM) is a classical optimization problem, which can be widely used in mobile networks, social computing, and recommendation systems. Main challenge comes from the NP-hardness of the IM problem and #P-hardness of estimating the influence spread. We focus on summarizing the relevant background knowledge, basic principles, common methods, and applied research.
  arXiv  Detail & Related papers  (2022-11-06T10:13:42Z)
• MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers [13.790116387956703]
  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.
  arXiv  Detail & Related papers  (2022-05-27T19:34:14Z)
• Optimizing Objective Functions from Trained ReLU Neural Networks via Sampling [0.0]
  This paper introduces scalable, sampling-based algorithms that optimize trained neural networks with ReLU activations. We first propose an iterative algorithm that takes advantage of the piecewise linear structure of ReLU neural networks. We then extend this approach by searching around the neighborhood of the LP solution computed at each iteration.
  arXiv  Detail & Related papers  (2022-05-27T18:35:48Z)
• A survey on multi-objective hyperparameter optimization algorithms for Machine Learning [62.997667081978825]
  This article presents a systematic survey of the literature published between 2014 and 2020 on multi-objective HPO algorithms. We distinguish between metaheuristic-based algorithms, metamodel-based algorithms, and approaches using a mixture of both. We also discuss the quality metrics used to compare multi-objective HPO procedures and present future research directions.
  arXiv  Detail & Related papers  (2021-11-23T10:22:30Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  Real-world applications typically require finding good solutions early in the search to enable fast decision-making. We propose the first data-driven framework for schedulings in an exact MIP solver. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances.
  arXiv  Detail & Related papers  (2021-03-18T14:49:52Z)
• 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)

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.