Integer and Combinatorial Optimization: Polyhedral Methods and Algorithms

本研究涉及整数和组合规划的理论和算法方面。其中的理论问题有：约束矩阵系数为0、1或-1的组合优化问题何时为可解线性规划（平衡的0、+1、-1矩阵）；如何在高维空间中重述给定的问题，以便将其投射回原始空间，从而产生更好的公式（提升/投射技术）；对于给定的拉格朗日公式，如何找到一个有效的不等式，将其包含到拉格朗日公式中，保证改进后者提供的界（面分离问题）。本课题的算法目标是：基于升降和项目切割的0-1混合方案的高效分支和切割算法；基于新识别面的使用，改进了旅行推销员问题及其相关问题的边界程序，并期望对困难的工业调度问题和几种作业车间调度问题产生改进的算法。

This research addresses theoretical and algorithmic aspects of integer and combinatorial programming. Among the theoretical questions are: when is a combinatorial optimization problem whose constraint matrix has coefficients of 0, 1, or -1 solvable as a linear program (balanced 0, +1, -1 matrices); how can one restate a given problem in a higher dimensional space so that projecting it back on the original space results in a better formulation (lifting/projecting techniques); for a given Lagrangean formulation, how can one find a valid inequality whose inclusion into the Lagrangean is guaranteed to improve the bound provided by the latter (the face separation problem). Among the algorithmic objectives of the project are: an efficient branch and cut algorithm for mixed 0-1 programs based on lift and project cuts; improved bounding procedures for the traveling salesman problem and some of its relatives, based on the use of newly identified facets, and expected to produce improved algorithms for difficult industrial scheduling problems and several types of job shop scheduling problems.