Theoretical challenges towards cutting-plane selection

• 成果类型: Article; Proceedings Paper
• 署名作者: Dey, Santanu S.; Molinaro, Marco
• 署名单位: University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1302-4
• 发表日期: 2018
• 页码: 237-266
• 关键词: lift-and-project; cut-generating functions; valid inequalities; extreme functions; Lower bounds; gomory cuts; convex-hull; relative strength; intersection cuts; corner polyhedra

摘要

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.