Local Cuts in Discrete Optimization and Mixed-Integer Programming

离散优化和混合整数规划中的局​​部削减

• 批准号: 0245609
• 负责人: William Cook
• 金额: $ 37.5万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-05-01 至 2007-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0245609&HistoricalAwards=false
• 关键词: Local; Cuts; Discrete; Optimization; Mixed

Solution algorithms for difficult discrete optimization problems often rely on problem-specific cutting-planes to improve the associated linear-programming relaxations. It is standard practice to look for cutting planes that match prescribed templates, where the templates are drawn exclusively from the set of linear inequalities that induce facets of the convex hull of the solution set for the problem. In the traveling salesman problem (TSP) research of Applegate, Bixby, Chvatal, and Cook, an alternative to this template paradigm for cutting planes was proposed. The new procedure is called local cuts and it played a crucial role in the solution of a set of large-scale TSP instances, including a 13,509-city example and a 15,112-city example. The goal of this project is to extend the local-cut procedure to other classes of discrete optimization problems and to general mixed-integer programming models. The local-cut procedure consists of selecting a family of linear mappings taking the original solution space down to one of low dimension, and selecting a super-set of the image that is accessible, that is, it is easy to optimize linear functions over the super-set. Using delayed column-generation, cutting planes for the accessible set are determined; these cuts are then mapped back to cutting planes in the original set of variables. This project will continue the investigation of local cuts for the TSP, but a major part of the work will be to develop the methodology for other classes of problems, including mixed-integer programming models, vehicle routing, steiner trees, and stable sets.Broader Impact. Discrete optimization is used to solve practical problems that involve choosing the best alternative from a field of possibilities; it has broad applications in nearly every segment of the economy. The local-cut techniques developed in the proposed project will permit the solution of larger, more-complex problem instances, allowing users to be more aggressive in building models to represent the details of their applications.

困难的离散优化问题的求解算法往往依赖于特定问题的切割平面，以改善相关的线性规划松弛。 标准做法是寻找与规定模板匹配的切割平面，其中模板专门从线性不等式集合中绘制，所述线性不等式集合导出问题的解集的凸船体的小平面。 在Applegate、Bixby、Chvatal和Cook对旅行商问题（TSP）的研究中，提出了一种替代切割平面的模板范式。 新的方法被称为局部割，它在一组大规模TSP实例的解决方案中发挥了关键作用，包括13,509个城市的例子和15,112个城市的例子。 本计画的目标是将局部切割程序延伸至其他类别的离散最佳化问题以及一般的混合整数规划模型。 局部切割过程包括选择一个家庭的线性映射采取原来的解决方案空间下降到一个低维，并选择一个超集的图像是可访问的，也就是说，它是很容易优化的超集上的线性函数。 使用延迟的列生成，确定可访问集合的切割平面;然后将这些切割映射回原始变量集合中的切割平面。 该项目将继续调查TSP的局部削减，但工作的主要部分将是开发其他类别的问题，包括混合整数规划模型，车辆路径，斯坦纳树和稳定集的方法。 离散优化用于解决实际问题，涉及从可能性领域中选择最佳方案;它在经济的几乎每个部门都有广泛的应用。在拟议项目中开发的局部切割技术将允许解决更大，更复杂的问题实例，允许用户更积极地构建模型来表示其应用程序的细节。