Research Initiation: Analysis of Linear Programming Relaxations of Combinatorial Optimization Problems

研究启动：组合优化问题的线性规划松弛分析

• 批准号: 9010322
• 负责人: Dimitris Bertsimas
• 金额: $ 5万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-07-01 至 1993-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9010322&HistoricalAwards=false
• 关键词: Research; Initiation; Analysis; Linear; Programming

Linear programming methods have proven invaluable in solving a wide variety of different applications of combinatorial optimization. Based on the belief that a better understanding of the properties of linear programming (LP) relaxations of integer programming formulations can be useful in obtaining additional insights concerning the problem itself and concerning how to formulate and solve it efficiently, LP relaxations will be investigated for several closely related generic combinatorial optimization problems: the network design problem with edge connectivity requirements, the Steiner tree problem, the traveling salesman problem and the vehicle routing problem. The tightness of these linear relaxations will be analyzed from three perspectives: worst-case, probabilistic and algorithmic. Research will take advantage of the interplay between different areas, such as polyhedral theory, probabilistic analysis, network flows, graph theory and randomized algorithms. The research will be divided into three tracks. In track 1, the relative tightness of different relaxations will be investigated, worst-case behavior of relaxations as compared to the optimal solution will be analyzed and the values obtained by heuristics for a particular combinatorial optimization problem will be related to different LP relaxations. In track 2, probabilistic analysis of various LP relaxation will be performed and the idea of randomized rounding for constructing a solution to the combinatorial optimization problem from its LP relaxation will be examined. In track 3, algorithms to compute the LP relaxations will be developed and the tightness of LP relaxation as well as the use of tight LP relaxations in large scale optimization algorithms will be investigated computationally.

线性规划方法已被证明在解决 各种不同的应用组合 优化. 基于这样的信念， 整数线性规划松弛的性质 编程公式可以用于获得额外的 关于问题本身以及如何 有效地制定和解决它，LP松弛将是 研究了几个密切相关的通用组合 优化问题：边的网络设计问题 连通性要求，Steiner树问题， 销售员问题和车辆路径问题。 面紧张 这些线性弛豫将分析从三个 观点：最坏情况，概率和算法。 研究 将利用不同领域之间的相互作用， 多面体理论，概率分析，网络流，图 理论和随机算法。 研究将分为 分成三条轨道。 在轨道1中， 将对松弛进行研究， 将分析与最优解相比的弛豫 以及通过化学分析获得的特定 组合优化问题将涉及到不同的LP 放松 在轨道2中，各种LP的概率分析 将进行放松，随机取整的想法 为了构造组合优化的解， 从LP松弛的问题将被检查。 在第三轨道， 将开发计算LP松弛的算法， LP松弛的紧度以及紧LP的使用 大规模优化算法中的松弛将是 通过计算研究。