Theoretical challenges towards cutting-plane selection

2018/05/07 by Dey, Santanu S., Molinaro, Marco · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1805.02782

Abstract

While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of selecting a portfolio of cutting-planes to be added to the LP relaxation at a given node of the branch-and-bound tree. In this paper we review the different classes of cutting-planes available, known theoretical results about their relative strength, important issues pertaining to cut selection, and discuss some possible new directions to be pursued in order to accomplish cutting-plane selection in a more principled manner. Finally, we review some lines of work that we undertook to provide a preliminary theoretical underpinning for some of the issues related to cut selection.

Cited by

• An Expansion-Based Approach for Quantified Integer Programming

Related

• Complexity of branch-and-bound and cutting planes in mixed-integer optimization -- II
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
• Cutting Plane Selection with Analytic Centers and Multiregression
• The Cutting Plane Method is Polynomial for Perfect Matchings
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond