CAREER: Non-traditional Cutting-Plane Algorithms for Mixed-Integer Programs

该学院早期职业发展(CALEAR)项目的研究目标是通过设计新的通用割平面方法来改进当前一代的混合整数规划(MIP)求解器。最先进的MIP技术往往没有使用大量可用于推导和选择切割平面的有用信息。本项目将研究以下一些将更多信息合并到剖切平面中的非传统范例：(I)同时使用来自多个约束的信息来推导剖切平面，而不是使用单个隐含约束。(Ii)设计合适的切割面，然后在使用前验证其有效性，而不是在没有对其质量进行任何控制的情况下推导切割面。(3)结合整数点显式计数的信息，指导切割平面的选择，提高切割平面的强度。由于需要克服许多数学挑战，以挖掘这些非传统范例的潜力，因此该项目的结果可以大大增强整数程序员用来生成和分析切割平面的数学工具包。如果成功，该项目不仅将在数学规划方面取得理论上的进展，还将显著提高MIP解算器的性能，使MIP模型在医疗保健、林业、金融、供应链设计和化学工程等领域的广泛应用中获得巨大收益。该奖项的主要教育目标是开展课外运筹学益智竞赛，以培养和丰富本科生的研究环境。此外，还将设计一个新的研究生课程，目的是将研究成果直接传播给未来的实践者，并将来自不同工程界的学生聚集在一起，从而为新的研究方向和合作提供机会。

The research objective of this Faculty Early Career Development (CAREER) project is to improve the current generation of mixed-integer programming (MIP) solvers by devising new general-purpose cutting-plane methods. A great deal of useful information that could be used in deriving and selecting cutting-planes is often left unused by state-of-the-art MIP techniques. This project will investigate some of the following non-traditional paradigms for incorporating more information into cutting planes: (i) Use information from multiple constraints simultaneously to derive cutting planes, instead of using a single implied constraint. (ii) Design suitable cutting planes and then verify their validity before use, instead of deriving cutting planes without any control over their quality. (iii) Incorporate information from explicit enumeration of integer points to guide the choice of cutting planes and improve their strength. Since many mathematical challenges need to be overcome in order to tap the potential of these non-traditional paradigms, results from this project could significantly enhance the mathematical toolkit used by integer programmers for the generation and analysis of cutting planes. If successful, this project will not only make theoretical advances in mathematical programming, but also lead to significant improvements in the performance of MIP solvers, leading to huge gains in a broad spectrum of applications of MIP models in areas such as health care, forestry, finance, supply-chain design, and chemical engineering. The key educational objective of this award is to develop an outside-classroom operations research puzzle competition to foster and enrich an environment for undergraduate research. Moreover a new graduate course will be designed with the aim of dissemination of research results directly to future practitioners and to bring students from different engineering communities together, thus providing opportunities for new research directions and collaborations.