Integer Programming and Combinatorial Optimization

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

The theme of this research is the investigation of the structural properties of various classes of discrete optimization problems, and the development of new solution methods capable of extending the sphere of problems that are currently tractable. The work covers various topics in integer and combinatorial programming, a theory and methodology with a wide range of applications. Some of the objectives of the research are: identifying new facets of the set covering polytope, with a view to using them as cutting planes; developing and testing new types of randomized heuristics for set covering; identifying new classes of graphs for which the vertex packing problem is polynomially solvable; developing disjunctive programming techniques for tighter formulations of mixed integer programs; applying disjunctive programming and polyhedral combinatorics to expert system design; decomposing vehicle routing problems; and devising new relaxations for the traveling salesman problem. The expected outcome of the research is both new structural insights and efficient solution procedures.