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.
