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

本学院早期职业发展（Career）项目的研究目标是通过设计新的通用切割平面方法来改进当前一代的混合整数规划（MIP）求解器。在最先进的MIP技术中，有很多有用的信息可以用来推导和选择切割平面，但这些信息往往没有被利用。本项目将研究以下一些将更多信息纳入切割平面的非传统范例：(i)同时使用来自多个约束的信息来推导切割平面，而不是使用单个隐含约束。（ii）设计合适的切割平面，并在使用前验证其有效性，而不是在不控制其质量的情况下推导切割平面。（iii）结合整数点的显式枚举信息，指导切割平面的选择，提高切割平面的强度。由于为了挖掘这些非传统范例的潜力，需要克服许多数学挑战，因此该项目的结果可以显著增强整数程序员用于生成和分析切割平面的数学工具包。如果成功，该项目不仅将在数学规划方面取得理论进展，而且还将显著改善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.