Mixed Integer Optimization: New Cut Generation Paradigms

几十年来，混合整数优化一直是一种非常通用的建模工具，但它只能解决相当小规模的实际问题。在过去的20年里，混合整数优化经历了一场真正的革命，极大地提高了我们解决工程、交通、电信、制造、能源生产、金融、营销和许多其他经济活动领域的实际问题的能力。这场革命的一个关键因素是将通用切割平面整合到求解器中，这是由九十年代初的主要研究人员在以前的国家科学基金会项目下设计的升降机和项目切割引发的，以及随后的Gomory混合整数切割的复兴，也是由以前的国家科学基金会支持的主要研究人员提倡的。本研究的目的是研究新的切割平面范式，旨在为混合整数优化解的转换带来另一个阶段。预计该项目开发的工具将产生广泛的影响，并将有助于加强美国的技术领导地位。该项目还将有助于参与研究的博士生的教育和培训。目前混合整数优化解中使用的切割平面大多对经典角点松弛有效，但角点松弛有时会相当弱。主要研究人员计划开发新的范式，以构建更丰富的切割族：从预先生成的点族中以非递归的方式产生广义相交切割；切割生成函数的一般理论允许通过封闭形式的公式生成切割。这些和其他旨在产生更强切割的理论结果，将与在解决混合整数优化问题的整个过程中对其效率的计算研究相结合。本研究中使用的工具将来自线性代数，如投影和提升，来自凸分析，如支持函数和极性，来自几何，如凸壳生成，来自晶格理论，如最大无晶格凸集和基约简，以及有效实现的算法技术。本课题有望完善组合优化和混合整数优化的知识库，扩展混合整数优化求解器的算法工具箱。和过去一样，由主要研究人员和他们的博士生开发的软件将是开源的，可以在网络上使用。

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.