Mixed Integer Optimization: New Cut Generation Paradigms

几十年来，混合整数优化一直是一种功能惊人的通用建模工具，但它只能解决相当小规模的实际问题。在过去的20年里，混合整数优化经历了一场真正的革命，极大地增强了我们解决工程、交通、电信、制造、能源发电、金融、营销和许多其他经济活动领域的实际问题的能力。这场革命的一个关键因素是将通用切割平面纳入求解器，这是由主要调查人员在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.