Integer and Combinatorial Optimization: Polyhedral Methods and Algorithms

点击翻译按钮获取中文摘要

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.