Combinatorial Optimization and Integer Programming: Polyhedral Analysis and Algorithms

9802773 BALAS由这笔赠款资助的研究涉及整数和组合优化的一些基本理论和方法方面。在过去的几年里，主要研究人员开发了一种名为Lift-and-Project的技术，用于求解混合整数规划。当嵌入到称为分支和切割的枚举式框架中时，这种方法已经显示出它自己非常健壮并且与最好的可用替代方案竞争。这项研究的一个主要目标是巩固这些结果，并通过解决有关所用割面的性质、生成和处理它们的方式以及切割和分支之间的相互作用等几个公开问题，将该方法发展到新的方向。这项研究的一部分将把多面体方法与借鉴人工智能的一些工具结合起来。一个密切相关的研究主题集中在一种名为辛烷的启发式程序上，该程序使用基于极性的结构定义的邻域搜索。另一个主题涉及理想0-1矩阵，它使由理想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.