Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming

• URL: http://arxiv.org/abs/2401.17527v2
• Date: Fri, 2 Feb 2024 05:54:58 GMT
• Title: Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming
• Authors: Haotian Ling, Zhihai Wang, Jie Wang
• Abstract summary: Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs) A key problem for cuts is when to stop cuts generation, which is important for the efficiency of solving MILPs. We propose a novel hybrid graph representation model (HYGRO) to learn effective stopping strategies.
• Score: 4.85018419433297
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs), as they significantly tighten the dual bounds and improve the solving performance. A key problem for cuts is when to stop cuts generation, which is important for the efficiency of solving MILPs. However, many modern MILP solvers employ hard-coded heuristics to tackle this problem, which tends to neglect underlying patterns among MILPs from certain applications. To address this challenge, we formulate the cuts generation stopping problem as a reinforcement learning problem and propose a novel hybrid graph representation model (HYGRO) to learn effective stopping strategies. An appealing feature of HYGRO is that it can effectively capture both the dynamic and static features of MILPs, enabling dynamic decision-making for the stopping strategies. To the best of our knowledge, HYGRO is the first data-driven method to tackle the cuts generation stopping problem. By integrating our approach with modern solvers, experiments demonstrate that HYGRO significantly improves the efficiency of solving MILPs compared to competitive baselines, achieving up to 31% improvement.

Related papers

• CHARME: A chain-based reinforcement learning approach for the minor embedding problem [16.24890195949869]
  We propose a novel approach utilizing Reinforcement Learning (RL) techniques to address the minor embedding problem, named CHARME. CHARME includes three key components: a Graph Neural Network (GNN) architecture for policy modeling, a state transition algorithm ensuring solution validity, and an order exploration strategy for effective training. In details, CHARME yields superior solutions compared to fast embedding methods such as Minorminer and ATOM.
  arXiv  Detail & Related papers  (2024-06-11T10:12:10Z)
• Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming [61.59888010725235]
  Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs) We propose a novel hierarchical sequence/set model (HEM) to learn cut selection policies. HEM is the first data-driven methodology that tackles well (P1)-(P3) simultaneously.
  arXiv  Detail & Related papers  (2024-04-19T05:40:25Z)
• GRASP: Accelerating Shortest Path Attacks via Graph Attention [1.3270612461223892]
  Recent advances in machine learning (ML) have shown promise in aiding and accelerating classical optimization algorithms. We propose the GRASP algorithm: Graph Accelerated Shortest Path Attack, an ML aided optimization algorithm that achieves run times up to 10x faster.
  arXiv  Detail & Related papers  (2023-10-12T02:03:10Z)
• Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model [81.56473654324328]
  We propose a novel hierarchical sequence model (HEM) to learn cut selection policies via reinforcement learning. HEM is the first method that can tackle (P1)-(P3) in cut selection simultaneously from a data-driven perspective. Experiments show that HEM significantly improves the efficiency of solving MILPs compared to human-designed and learning-based baselines.
  arXiv  Detail & Related papers  (2023-02-01T04:59:55Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning [80.45697245527019]
  We show that a greedy selection rule explicitly looking ahead to select cuts that yield the best bound improvement delivers strong decisions for cut selection. We propose a new neural architecture (NeuralCut) for imitation learning on the lookahead expert.
  arXiv  Detail & Related papers  (2022-06-27T16:07:27Z)
• 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)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  We propose a practical online method for solving a class of online distributionally robust optimization (DRO) problems. Our studies demonstrate important applications in machine learning for improving the robustness of networks.
  arXiv  Detail & Related papers  (2020-06-17T20:19:25Z)

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.