Polyhedral Cutting Planes for General Mixed-Integer Programming

本研究项目解决了对一般混合整数规划问题的多面体（几何）结构理解上的差距。以开发具有一般整数变量的混合整数问题的高效切割平面程序为最终目标，将通过对基本单约束混合整数集的多面体分析来确定适用于一般混合整数问题的强切割平面。本文的研究方法是基于最近在一般混合整数规划中利用超加性函数对有效不等式的序列无关提升的研究成果。本研究项目的预期成果是将新的切割平面程序纳入解决大规模混合整数规划问题的分支-切割算法。如果成功，该研究项目可能会导致对一般混合整数多面体的理解以及具有一般整数变量的混合整数问题的大规模实例的解决方法的重大进展。

This research project addresses the gap in the understanding of the polyhedral (geometric) structure of general mixed-integer programming problems. With an ultimate goal of developing efficient and effective cutting plane procedures for mixed-integer problems with general integer variables, strong cutting planes applicable to general mixed-integer problems will be identified through polyhedral analysis of fundamental single-constraint mixed-integer sets. The methods of the research are based on a recent work on sequence independent lifting of valid inequalities through the use of superadditive functions for general mixed-integer programming. The expected outcome of this research project is novel cutting plane procedures that will be incorporated in branch-and-cut algorithms for solving large-scale mixed-integer programming problems. If successful, the research project may lead to significant advances in the understanding of general mixed-integer polyhedra and in the solution methods for large-scale instances of mixed-integer problems with general integer variables.