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

线性规划方法在解决组合优化的各种不同应用方面已被证明是非常有价值的。基于这样一种信念，即更好地理解整数规划公式的线性规划(LP)松弛的性质对于获得关于问题本身以及关于如何有效地表述和求解问题本身的额外见解是有用的，将研究几个密切相关的一般组合优化问题的LP松弛：具有边连通性要求的网络设计问题，Steiner树问题，旅行商问题和车辆路径问题。这些线性松弛的紧密性将从三个角度进行分析：最坏情况、概率和算法。研究将利用不同领域之间的相互作用，如多面体理论、概率分析、网络流、图论和随机算法。这项研究将分为三个轨道。在轨道1中，将研究不同松弛的相对紧密性，将分析松弛相对于最优解的最坏情况行为，并且通过启发式获得的特定组合优化问题的值将与不同的LP松弛相关。在第二轨道中，将对各种LP松弛进行概率分析，并将研究从LP松弛构造组合优化问题的解的随机舍入的想法。在第三轨道中，将开发计算Lp松弛的算法，并将通过计算研究Lp松弛的紧性以及紧Lp松弛在大规模优化算法中的使用。

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.