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.