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进行当地削减的调查，但其中的主要部分是为其他类别的问题开发方法，包括混合成员编程模型，车辆路线，Steiner树和稳定的套装。 离散优化用于解决实际问题，涉及从可能性领域中选择最佳替代方案；它在几乎每个经济领域都有广泛的应用。在拟议项目中开发的本地切割技术将允许解决更大，更复杂的问题实例的解决方案，从而使用户在构建模型中更具侵略性，以代表其应用程序的细节。