Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming

• URL: http://arxiv.org/abs/2404.12638v1
• Date: Fri, 19 Apr 2024 05:40:25 GMT
• Title: Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming
• Authors: Jie Wang, Zhihai Wang, Xijun Li, Yufei Kuang, Zhihao Shi, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, Feng Wu,
• Abstract summary: 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.
• Score: 61.59888010725235
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs), which formulate many important real-world applications. Cut selection heavily depends on (P1) which cuts to prefer and (P2) how many cuts to select. Although modern MILP solvers tackle (P1)-(P2) by human-designed heuristics, machine learning carries the potential to learn more effective heuristics. However, many existing learning-based methods learn which cuts to prefer, neglecting the importance of learning how many cuts to select. Moreover, we observe that (P3) what order of selected cuts to prefer significantly impacts the efficiency of MILP solvers as well. To address these challenges, we propose a novel hierarchical sequence/set model (HEM) to learn cut selection policies. Specifically, HEM is a bi-level model: (1) a higher-level module that learns how many cuts to select, (2) and a lower-level module -- that formulates the cut selection as a sequence/set to sequence learning problem -- to learn policies selecting an ordered subset with the cardinality determined by the higher-level module. To the best of our knowledge, HEM is the first data-driven methodology that well tackles (P1)-(P3) simultaneously. Experiments demonstrate that HEM significantly improves the efficiency of solving MILPs on eleven challenging MILP benchmarks, including two Huawei's real problems.

Related papers

• Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming [4.85018419433297]
  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.
  arXiv  Detail & Related papers  (2024-01-31T01:09:40Z)
• Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning [92.31528918811007]
  We propose a simple and efficient reinforcement learning framework -- namely, reinforcement learning for presolve (RL4Presolve) -- to tackle (P1)-(P3) simultaneously. Experiments on two solvers and eight benchmarks (real-world and synthetic) demonstrate that RL4Presolve significantly and consistently improves the efficiency of solving large-scale LPs.
  arXiv  Detail & Related papers  (2023-10-18T09:51:59Z)
• Improving Large Language Model Fine-tuning for Solving Math Problems [20.417053742869403]
  A large gap exists between large language models' pass-at-one and pass-at-N performance in solving math problems. Using the challenging MATH dataset, we investigate three fine-tuning strategies. We design a fine-tuning recipe that yields approximately 58.8% accuracy on the MATH dataset with fine-tuned PaLM 2-L models.
  arXiv  Detail & Related papers  (2023-10-16T04:11:19Z)
• 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 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)
• The Paradox of Choice: Using Attention in Hierarchical Reinforcement Learning [59.777127897688594]
  We present an online, model-free algorithm to learn affordances that can be used to further learn subgoal options. We investigate the role of hard versus soft attention in training data collection, abstract value learning in long-horizon tasks, and handling a growing number of choices.
  arXiv  Detail & Related papers  (2022-01-24T13:18:02Z)
• Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
  We propose a data-driven and generalizable cut selection approach, named Cut Ranking, in the settings of multiple instance learning. Cut Ranking has been deployed in an industrial solver for large-scale MIPs. It has achieved the average speedup ratio of 12.42% over the production solver without any accuracy loss of solution.
  arXiv  Detail & Related papers  (2021-05-28T07:48:34Z)

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.