By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Review

Previous Article
Instabilities in Gravity Driven Flow of Thin Fluid Films
This paper presents theoretical, computational, and experimental aspects of the instability development in the flow of thin fluid films. The theoretical part involves basic fluid mechanics and presen...
Next Article
Book Reviews
This issue begins with a featured review by Mark Lewis on the new, expanded version of Akira Okubo's classic Diffusion and Ecological Problems, updated by a team headed by Si Levin. Since so much has ...

You are logged in to this journal.

Teaching Integer Programming Formulations Using the Traveling Salesman Problem

SIAM Rev. Volume 45, Issue 1, pp. 116-123 (2003)

Issue Date: 2003
FULL TEXT OPTIONS   (FREE)
Download PDF (351 kB) View Cart

We designed a simple computational exercise to compare weak and strong integer programming formulations of the traveling salesman problem. Using commercial IP software, and a short (60 line long) MATLAB code, students can optimally solve instances with up to 70 cities in a few minutes by adding cuts from the stronger formulation to the weaker, but simpler one.

©2003 Society for Industrial and Applied Mathematics
Permalink: http://dx.doi.org/10.1137/S00361445023685

KEYWORDS and AMS

Keywords
AMS Subject Classifications
90C10, 90C11, 90C27, 90C57, 90-01, 97D40

PUBLICATION DATA

ISSN:
0036-1445 (print)   1095-7200 (online)
Publisher:
AIP is a member of CrossRef SIAM

REFERENCES (10)
View in Separate Window/Tab
  1. Egon Balas, Projection and lifting in combinatorial optimization, Lecture Notes in Comput. Sci., Vol. 2241, Springer, Berlin, 2001, 26–56 [MathRev]
  2. http://www.caam.rice.edu/~bico/, home page of Bill Cook at Rice University.
  3. http://www.keck.caam.rice.edu/concorde.html.
  4. E. Lawler, J. Lenstra, A. Rinnooy Kan, D. Shmoys, The traveling salesman problem, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons Ltd., 1985x+465, A guided tour of combinatorial optimization; A Wiley-Interscience Publication [ZentralblattMath] [MathRev]
  5. André Langevin, François Soumis, Jacques Desrosiers, Classification of travelling salesman problem formulations, Oper. Res. Lett., 9 (1990), 127–132
  6. C. Miller, A. Tucker, R. Zemlin, Integer programming formulation of traveling salesman problems, J. Assoc. Comput. Mach., 7 (1960), 326–329 [ISI]
  7. D. M. Panton and A. W. Elbers, Mission planning for synthetic aperture radar surveillance, Interfaces, 29 (1999), pp. 73–88.
  8. Manfred Padberg, Ting-Yi Sung, An analytical comparison of different formulations of the travelling salesman problem, Math. Programming, 52 (1991), 315–357
  9. Laurence Wolsey, Integer programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., 1998xx+264, A Wiley-Interscience Publication [MathRev]
  10. http://www.iwr.uni-heidelberg.de/iwr/comopt/software/TSPLIB95/.