Combinatorial Optimization and Integer Programming: Polyhedral Analysis and Algorithms

小行星9802773 该基金资助的研究涉及整数和组合优化的一些基本理论和方法学方面。在过去的几年里，主要的研究人员开发了一种称为提升和投影的技术来解决混合整数规划。当嵌入到一个枚举框架，称为分支和切割，这种方法已被证明是非常强大的和竞争力的最佳可用的替代品。研究的一个主要目标是巩固这些成果，并在新的方向发展的方法，通过解决几个开放的问题，有关使用的切割平面的属性;生成和处理它们的方式;和，切割和分支之间的相互作用。本研究的一部分将联合收割机多面体方法与从人工智能中借用的一些工具相结合。一个密切相关的研究课题是集中在一个启发式的程序称为OCTANE，它使用的邻域搜索定义的建设的基础上的极性。另一个主题涉及理想0-1矩阵，这使得由它们定义的某些整数规划可解为线性规划。最后，研究的很大一部分将集中在旅行商问题，以及它的一些推广，重点是动态规划方法，可以有效地解决这一领域的大类问题。 这里设想的研究，预计将大大提高在解决整数和组合优化问题，特别是旅行推销员型问题的最新技术水平。一些研究旨在获得新的理论见解和对所涉及结构的更深入理解，但大多数研究本质上是方法论的，因此预计会产生更有效的算法和计算机代码。这些算法可能适用的问题范围从投资决策，产能扩张模型，位置和分布问题，工业调度和排序。

9802773 Balas The research funded by this grant addresses some basic theoretical and methodological aspects of integer and combinatorial optimization. Over the last few years the principal investigators have developed a technique called lift-and-project for solving mixed integer programs. When embedded in an enumerative framework, called branch-and-cut, this approach has shown itself to be highly robust and competitive with the best available alternatives. A major goal of the research is to consolidate these results and develop the approach in new directions, by solving several open problems concerning the properties of the cutting planes used; the way of generating and handling them; and, the interplay between cutting and branching. Part of this research will combine polyhedral methods with some tools borrowed from artificial intelligence. A closely related research topic is focussed on a heuristic procedure called OCTANE, which uses a neighborhood search defined by a construction based on polarity. Another topic involves ideal 0-1 matrices, which make certain integer programs defined by them solvable as linear programs. Finally, a substantial part of the research will focus on the traveling salesman problem, and some of its generalizations, focusing on a dynamic programming approach that can efficiently solve large classes of problems in this area. The research envisaged here is expected to substantially enhance the state of the art in solving integer and combinatorial optimization problems in general, traveling salesman-type problems in particular. Some of the investigations are aimed at gaining new theoretical insights and a deeper understanding of the structures involved, but most of the research is methodological in nature and is therefore expected to result in more efficient algorithms and computer codes. The problems to which such algorithms may be applicable range from investment decisions, capacity expansion models, location and distribution problems, to industrial scheduling and sequencing.