Integer Programming Formulation of Traveling Salesman Problems

Integer Programming Formulation of Traveling Salesman Problems

April 1960 | C. E. MILLER, A. W. TUCKER, R. A. ZEMLIN
This paper presents an integer programming formulation of a generalized traveling salesman problem (TSP). The problem involves a salesman who must visit n cities, starting and ending at a base city (city 0), visiting each city exactly once, and returning to city 0 exactly t times, with no more than p cities visited in a single tour. The goal is to minimize the total distance traveled. The authors formulate this problem as an integer programming problem, where variables x_ij indicate whether the salesman travels from city i to city j, and u_i are auxiliary variables. The formulation includes constraints ensuring each city (except 0) is visited exactly once, and that tours do not begin or end at city 0 or exceed p cities. The constraints also ensure that tours include city 0. The paper shows that this integer programming formulation is equivalent to the original TSP problem. It also discusses the computational complexity of the problem, noting that the current integer programming procedures are not yet sufficient for solving the problem efficiently. However, the authors report results from five machine experiments, showing that the formulation is effective for small problems. The paper concludes that more efficient integer programming procedures are likely to yield a satisfactory algorithmic solution to the TSP when applied to this model. The model demonstrates how complex problems can be succinctly formulated in integer programming terms.This paper presents an integer programming formulation of a generalized traveling salesman problem (TSP). The problem involves a salesman who must visit n cities, starting and ending at a base city (city 0), visiting each city exactly once, and returning to city 0 exactly t times, with no more than p cities visited in a single tour. The goal is to minimize the total distance traveled. The authors formulate this problem as an integer programming problem, where variables x_ij indicate whether the salesman travels from city i to city j, and u_i are auxiliary variables. The formulation includes constraints ensuring each city (except 0) is visited exactly once, and that tours do not begin or end at city 0 or exceed p cities. The constraints also ensure that tours include city 0. The paper shows that this integer programming formulation is equivalent to the original TSP problem. It also discusses the computational complexity of the problem, noting that the current integer programming procedures are not yet sufficient for solving the problem efficiently. However, the authors report results from five machine experiments, showing that the formulation is effective for small problems. The paper concludes that more efficient integer programming procedures are likely to yield a satisfactory algorithmic solution to the TSP when applied to this model. The model demonstrates how complex problems can be succinctly formulated in integer programming terms.
Reach us at info@study.space