(Mixed) Integer and Combinatorial Optimization: New Convexification Techniques

这个研究项目的目标是研究可能进一步加速整数规划革命的新思想。该项目将研究更有效的凸化技术：一种新的切割平面范式，它产生一个可以产生切割的点池，以及一种切割生成函数理论，两者都旨在更有效地找到更深的切割。在过去的二十年里，整数规划经历了一场革命，它极大地提高了我们解决工程、制造、运输、电信、金融、营销和许多其他经济活动领域实际问题的能力。根据最近进行的广泛测试，整数规划求解器现在比20年前快了近10亿倍。更好的整数规划算法（包括它们的线性规划组件）使速度提高了大约50万倍，其余的改进（大约1600倍）来自更快的计算机。这种转变的一个关键因素是在90年代早期切割平面的使用上取得了突破，包括升降机和项目切割的设计以及随后的Gomory混合整数切割的复兴，这两个项目是由主要研究人员在以前的NSF支持下进行的。解决大规模混合整数线性规划的能力的进步将影响问题的解决，并提高极为广泛的活动中的操作效率，这些活动包括工业生产、供应链管理、物流、运输、电力生产、机场运营、电信网络、医疗保健应用（如安排重症监护病房和确定辐射剂量）、组合拍卖、金融和经济。该项目开发的工具的广泛影响将有助于技术卓越，并加强美国的技术领导地位。

The objective of this research project is to investigate new ideas that could potentially further accelerate the revolution in integer programming. This project will investigate more efficient convexification techniques: a new cutting plane paradigm that generates a pool of points from which cuts can be produced, and a theory of cut-generating functions, both aimed at finding deeper cuts more efficiently. Integer programming has experienced a revolution in the last two decades that has greatly advanced our ability to solve practical problems in engineering, manufacturing, transportation, telecommunication, finance, marketing and many other areas of economic activity. According to recently performed extensive testing, integer programming solvers are now close to a billion times faster than they were twenty years ago. Better integer programming algorithms (including their linear programming components) account for a speedup of about half a million times, the rest of the improvement (by a factor of about 1600) coming from faster computers. A key element of this transformation was a breakthrough in the use of cutting planes in the early nineties, including the design of the lift-and-project cuts and the ensuing revival of the Gomory mixed integer cuts, two projects carried out by the principal investigators with previous NSF support.Progress in the ability to solve large-scale mixed integer linear programs will affect problem solving and improve efficiency of operations in an extremely broad range of activities that include industrial production, supply chain management, logistics, transportation, electricity production, airport operations, telecommunication networks, health care applications such as scheduling intensive care units and determining radiation dosage, combinatorial auctions, finance and economics. The widespread impact of tools developed in this project will contribute to technological excellence and strengthen US technological leadership.