Mixed Integer Optimization: New Cut Generation Paradigms

在作为一个令人惊讶的多功能建模工具服务了几十年之后，但它只能解决相当小规模的实际问题，混合整数优化在过去的二十年中经历了一场真正的革命，大大提高了我们解决工程，运输，电信，制造，能源发电，金融，营销和许多其他经济活动领域实际问题的能力。这场革命的一个关键因素是将通用切割平面纳入求解器，这是由主要研究人员在90年代初根据之前的NSF项目设计的提升和投影切割以及随后的Gomory混合整数切割的复兴引发的，这也是主要研究人员在之前的NSF支持下倡导的。本研究的目的是探讨新的切割平面范式意味着带来另一个阶段的混合整数优化求解器的转换。该项目开发的工具预计将产生广泛的影响，它们将有助于加强美国的技术领导地位。 该项目还将有助于参与研究的博士生的教育和培训。目前用于混合整数优化求解器的大多数切割平面对于经典的角松弛是有效的，这有时是相当弱的。主要研究人员计划开发新的范式，使建设更丰富的家庭削减：广义交叉削减产生的非递归方式从家庭的点提前产生;一般理论的削减生成功能允许通过封闭形式的公式产生削减。这些和其他的理论结果，旨在产生更强的削减，将结合其效率的计算研究在整个过程中解决混合整数优化问题。在这项研究中使用的工具将来自线性代数，如投影和提升，从凸分析，如支持函数和极性，从几何，如凸船体生成，从格理论，如最大无格凸集和基础减少，沿着与算法技术，以有效地实现。这个项目可以预期推进组合和混合整数优化的知识库，并扩大混合整数优化求解器的算法工具包。与过去一样，主要研究人员及其博士生开发的软件将是开源的，并可在网上获得。

After having served for decades as an amazingly versatile modeling tool, but one that could only solve practical problems of rather small sizes, mixed-integer optimization has undergone a true revolution in the last twenty years, greatly enhancing our ability to tackle practical problems in engineering, transportation, telecommunications, manufacturing, energy generation, finance, marketing and many other areas of economic activity. A key factor in this revolution was the incorporation of general-purpose cutting planes into the solvers, triggered by the lift-and-project cuts designed by the principal investigators in the early nineties under a previous NSF project, and the subsequent revival of Gomory's mixed integer cuts, also advocated by the principal investigators with previous NSF support. The objective of this research is to investigate new cutting plane paradigms meant to bring about another phase in the transformation of mixed-integer optimization solvers. The tools developed in this project are expected to have a broad impact and they should contribute to strengthening US technological leadership. This project will also contribute to the education and training of the PhD students involved in the research.Most of the cutting planes currently used in mixed-integer optimization solvers are valid for the classical corner relaxation, which can sometimes be rather weak. The principal investigators plan to develop new paradigms that will enable the construction of much richer families of cuts: generalized intersection cuts are produced in a non-recursive fashion from a family of points generated in advance; a general theory of cut-generating functions allows the generation of cuts through closed-form formulas. These and other theoretical results, aimed at producing stronger cuts, will be combined with computational investigations of their efficiency within the overall process of solving mixed-integer optimization problems. The tools used in this research will come from linear algebra such as projection and lifting, from convex analysis such as support functions and polarity, from geometry such as convex hull generation, from lattice theory such as maximal lattice-free convex sets and basis reduction, along with algorithmic techniques for efficient implementation. This project can be expected to advance the knowledge base in combinatorial and mixed-integer optimization, and to expand the algorithmic tool kit for mixed-integer optimization solvers. As in the past, software developed by the principal investigators and their PhD students will be open source and available on the web.