Complex Integer Rounding Cuts for Mixed Integer Programming

该奖项的研究目标是创建和评估混合整数规划的新的切割平面方法，使用一种称为复整数舍入的新方法。切平面是求解混合整数规划问题算法的关键部分。混合整数规划是一种优化框架，在科学、工程和商业中有着广泛的应用。所提出的方法包括导出三个主要元素的新形式并创新地使用它们：在将原始约束和一系列中间不等式应用于松弛/组合过程中，利用基本多面体的一个或多个面和/或一个或多个子加性函数来最终获得切割生成函数。将考虑单约束和多约束切割，并研究已开发切割的面定义属性。对一系列重要的特殊结构问题的切割定制将进行研究。为了评估开发的切割的性能，将开发有效的分离方法并进行全面的计算实验。混合整数规划是一种强大而灵活的优化范例，在从机组调度到分子生物学的科学、工程和商业领域都有广泛的应用。然而，求解混合整数程序通常是非常困难的。通过引入新的强切割平面，这项研究如果成功，将导致更快的混合整数规划求解算法，并将增加我们能够解决的问题的规模。因此，它将对上述所有领域产生重大影响。此外，本研究的方法学发展为切割平面方法的几个新的研究途径打开了大门。

The research objective of this award is to create and evaluate new cutting plane methods for mixed integer programming using a new approach here called Complex Integer Rounding. Cutting planes are a crucial part of the algorithms used for solving mixed integer programming problems. Mixed integer programming is an optimization framework with numerous applications in science, engineering, and business. The proposed approach consists of deriving novel forms of three major elements and making innovative use of them: one or multiple facets of base polyhedra and/or one or multiple sub-additive functions are utilized within a relaxation/combination procedure which is applied on the original constraints and a series of intermediate inequalities to eventually obtain a cut generator function. Both single-constraint and multi-constraint cuts will be considered and facet-defining properties of the developed cuts will be investigated. The customization of the cuts to a collection of important special-structure problems will be studied. In order to evaluate performance of the developed cuts, efficient separation methods will be developed and comprehensive computational experiments will be performed.Mixed integer programming is a powerful and flexible optimization paradigm with ubiquitous applications in science, engineering, and business ranging from flight crew scheduling to molecular biology. Yet solving mixed integer programs is generally very difficult. Through introduction of new strong cutting planes, this research, if successful, will result in faster solution algorithms for mixed integer programming and will increase the size of the problems that we are able to solve. Consequently, it will have a significant impact on all aforementioned areas. Moreover, the methodological developments in this research open doors to several new research avenues regarding cutting plane methods.