Learning to select cuts for efficient mixed-integer programming

Advanced search
Browse by:

Department | Year

UCL Theses | Latest

Deposit your research

Learning to select cuts for efficient mixed-integer programming

Huang, Zeren; Wang, Kerong; Liu, Furui; Zhen, Hui-Ling; Zhang, Weinan; Yuan, Mingxuan; Hao, Jianye; ... Wang, Jun; + view all (2022) Learning to select cuts for efficient mixed-integer programming. Pattern Recognition , 123 , Article 108353. 10.1016/j.patcog.2021.108353. Green open access

Preview

Text
2105.13645v3.pdf - Accepted Version
Download (595kB) | Preview

Abstract

Cutting plane methods play a significant role in modern solvers for tackling mixed-integer programming (MIP) problems. Proper selection of cuts would remove infeasible solutions in the early stage, thus largely reducing the computational burden without hurting the solution accuracy. However, the major cut selection approaches heavily rely on heuristics, which strongly depend on the specific problem at hand and thus limit their generalization capability. In this paper, we propose a data-driven and generalizable cut selection approach, named CUT RANKING, in the settings of multiple instance learning. To measure the quality of the candidate cuts, a scoring function, which takes the instance-specific cut features as inputs, is trained and applied in cut ranking and selection. In order to evaluate our method, we conduct extensive experiments on both synthetic datasets and real-world datasets. Compared with commonly used heuristics for cut selection, the learning-based policy has shown to be more effective, and is capable of generalizing over multiple problems with different properties. CUT RANKING has been deployed in an industrial solver for large-scale MIPs. In the online A/B testing of the product planning problems with more than 107 variables and constraints daily, CUT RANKING has achieved the average speedup ratio of 12.42% over the production solver without any accuracy loss of solution.

Type:	Article
Title:	Learning to select cuts for efficient mixed-integer programming
Open access status:	An open access version is available from UCL Discovery
DOI:	10.1016/j.patcog.2021.108353
Publisher version:	https://doi.org/10.1016/j.patcog.2021.108353
Language:	English
Additional information:	This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords:	Science & Technology, Technology, Computer Science, Artificial Intelligence, Engineering, Electrical & Electronic, Computer Science, Engineering, Mixed-Integer programming, Cutting plane, Multiple instance learning, Generalization ability
UCL classification:	UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL
URI:	https://discovery.ucl.ac.uk/id/eprint/10154111