January, 1960; revised June, 1960 | C. E. MILLER, A. W. TUCKER, R. A. ZEMLIN
The paper by C. E. Miller, A. W. Tucker, and R. A. Zemlin presents an integer programming formulation of a generalized version of the Traveling Salesman Problem (TSP). The problem involves a salesman who must visit each of \( n \) cities exactly once, return to the starting city \( t \) times, and visit no more than \( p \) cities in one tour. The goal is to minimize the total distance traveled. The authors develop an integer programming model with \( n^2 + n \) constraints and \( n^2 + 2n \) variables, which is efficient in terms of generality, variables, and constraints. They demonstrate that this model is equivalent to the TSP by showing that feasible solutions to the integer program correspond to valid TSP tours. The paper also reports on five machine experiments using an all-integer algorithm by R. E. Gomory, which show that the current formulation can solve smaller instances of the TSP efficiently. The authors conclude that more efficient integer programming procedures are expected to provide satisfactory solutions to the TSP when applied to this model.The paper by C. E. Miller, A. W. Tucker, and R. A. Zemlin presents an integer programming formulation of a generalized version of the Traveling Salesman Problem (TSP). The problem involves a salesman who must visit each of \( n \) cities exactly once, return to the starting city \( t \) times, and visit no more than \( p \) cities in one tour. The goal is to minimize the total distance traveled. The authors develop an integer programming model with \( n^2 + n \) constraints and \( n^2 + 2n \) variables, which is efficient in terms of generality, variables, and constraints. They demonstrate that this model is equivalent to the TSP by showing that feasible solutions to the integer program correspond to valid TSP tours. The paper also reports on five machine experiments using an all-integer algorithm by R. E. Gomory, which show that the current formulation can solve smaller instances of the TSP efficiently. The authors conclude that more efficient integer programming procedures are expected to provide satisfactory solutions to the TSP when applied to this model.