Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning

• URL: http://arxiv.org/abs/2206.13414v1
• Date: Mon, 27 Jun 2022 16:07:27 GMT
• Title: Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning
• Authors: Max B. Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, Chris J. Maddison
• Abstract summary: 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.
• Score: 80.45697245527019
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Cutting planes are essential for solving mixed-integer linear problems (MILPs), because they facilitate bound improvements on the optimal solution value. For selecting cuts, modern solvers rely on manually designed heuristics that are tuned to gauge the potential effectiveness of cuts. 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 - but is too expensive to be deployed in practice. In response, we propose a new neural architecture (NeuralCut) for imitation learning on the lookahead expert. Our model outperforms standard baselines for cut selection on several synthetic MILP benchmarks. Experiments with a B&C solver for neural network verification further validate our approach, and exhibit the potential of learning methods in this setting.

Related papers

• Learning to Remove Cuts in Integer Linear Programming [57.15699051569638]
  We consider the removal of previous cuts introduced at any of the preceding iterations of a method under a learnable parametric criteria. We demonstrate that in fundamental optimization settings such cut removal policies can lead to significant improvements over both human-based and machine learning-guided cut addition policies.
  arXiv  Detail & Related papers  (2024-06-26T22:50:43Z)
• 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)
• Deep Reinforcement Learning for Picker Routing Problem in Warehousing [0.6562256987706128]
  We introduce an attention based neural network for modeling picker tours, which is trained using Reinforcement Learning. A key advantage of our proposed method is its ability to offer an option to reduce the perceived complexity of routes.
  arXiv  Detail & Related papers  (2024-02-05T21:25:45Z)
• 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)
• Adaptive Cut Selection in Mixed-Integer Linear Programming [0.294944680995069]
  Cut selection is a subroutine used in all modern mixed-integer linear programming solvers. We present a family of mixed-integer linear programs together with infinitely many family-wide valid cuts. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values.
  arXiv  Detail & Related papers  (2022-02-22T15:07:33Z)
• 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)
• End-to-end learnable EEG channel selection with deep neural networks [72.21556656008156]
  We propose a framework to embed the EEG channel selection in the neural network itself. We deal with the discrete nature of this new optimization problem by employing continuous relaxations of the discrete channel selection parameters. This generic approach is evaluated on two different EEG tasks.
  arXiv  Detail & Related papers  (2021-02-11T13:44:07Z)

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.