Theoretical challenges towards cutting-plane selection

Santanu S. Dey, Marco Molinaro

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.
BibTeX
@article{dey2018theoretical,
  author = {Santanu S. Dey and Marco Molinaro},
  title = {{Theoretical challenges towards cutting-plane selection}},
  journal = {Math. Program.},
  year = {2018},
  doi = {10.1007/s10107-018-1302-4},
}

Loading related content...

Figure