| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
13 February 2025 |
|
| | | |
|
Article overview
| |
|
Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model | Zhihai Wang
; Xijun Li
; Jie Wang
; Yufei Kuang
; Mingxuan Yuan
; Jia Zeng
; Yongdong Zhang
; Feng Wu
; | Date: |
1 Feb 2023 | Abstract: | Cutting planes (cuts) are important for solving mixed-integer linear programs
(MILPs), which formulate a wide range of important real-world applications. Cut
selection -- which aims to select a proper subset of the candidate cuts to
improve the efficiency of solving MILPs -- heavily depends on (P1) which cuts
should be preferred, and (P2) how many cuts should be selected. Although many
modern MILP solvers tackle (P1)-(P2) by manually designed heuristics, machine
learning offers a promising approach to learn more effective heuristics from
MILPs collected from specific applications. However, many existing
learning-based methods focus on learning which cuts should be preferred,
neglecting the importance of learning the number of cuts that should be
selected. Moreover, we observe from extensive empirical results that (P3) what
order of selected cuts should be preferred has a significant impact on the
efficiency of solving MILPs as well. To address this challenge, we propose a
novel hierarchical sequence model (HEM) to learn cut selection policies via
reinforcement learning. Specifically, HEM consists of a two-level model: (1) a
higher-level model to learn the number of cuts that should be selected, (2) and
a lower-level model -- that formulates the cut selection task as a sequence to
sequence learning problem -- to learn policies selecting an ordered subset with
the size determined by the higher-level model. To the best of our knowledge,
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 on both synthetic and large-scale
real-world MILPs, including MIPLIB 2017. Moreover, experiments demonstrate that
HEM well generalizes to MILPs that are significantly larger than those seen
during training. | Source: | arXiv, 2302.00244 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|