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.