Teaching Integer Programming Formulations Using the Traveling Salesman Problem
作者： Gábor Pataki
关键词:
摘要: We designed a simple computational exercise to compare weak and strong integer programming formulations of the traveling salesman problem. Using commercial IP software, short (60 line long) MATLAB code, students can optimally solve instances with up 70 cities in few minutes by adding cuts from stronger formulation weaker, but simpler one.
sci-hub.se 参考文章(6)
Manfred Padberg, Ting-Yi Sung, An analytical comparison of different formulations of the travelling sales man problem Mathematical Programming. ,vol. 52, pp. 315- 357 ,(1991) , 10.1007/BF01582894
André Langevin, François Soumis, Jacques Desrosiers, Classification of travelling salesman problem formulations Operations Research Letters. ,vol. 9, pp. 127- 132 ,(1990) , 10.1016/0167-6377(90)90052-7
C. E. Miller, A. W. Tucker, R. A. Zemlin, Integer Programming Formulation of Traveling Salesman Problems Journal of the ACM. ,vol. 7, pp. 326- 329 ,(1960) , 10.1145/321043.321046
David M. Panton, Anita W. Elbers, Mission Planning for Synthetic Aperture Radar Surveillance Interfaces. ,vol. 29, pp. 73- 88 ,(1999) , 10.1287/INTE.29.2.73
D.B. Shmoys, E.L. Lawler, Jan Karel Lenstra, A.H.G. Rinnooy Kan, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization ,(1985)
L. A. Wolsey, G. L. Nemhauser, Integer programming ,(1972)