Combinatorial Optimization and Integer Programming: Polyhedral Analysis and Algorithms

[9802773] Balas这项基金资助的研究涉及整数和组合优化的一些基本理论和方法方面。在过去的几年里，主要的研究人员开发了一种称为提升和项目的技术来解决混合整数程序。当嵌入到称为“分支-切断”的枚举框架中时，这种方法显示出高度健壮性，并且与最佳可用替代方案具有竞争力。该研究的一个主要目标是通过解决有关所用切割平面特性的几个开放问题，巩固这些结果并在新的方向上发展该方法；产生和处理它们的方式；切割和分支之间的相互作用。这项研究的一部分将把多面体方法与借鉴人工智能的一些工具结合起来。一个密切相关的研究主题集中在一个启发式过程，称为辛烷值，它使用一个基于极性的结构定义的邻域搜索。另一个主题涉及理想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.