An analytical comparison of different formulations of the travelling salesman problem
Tóm tắt
Từ khóa
Tài liệu tham khảo
J.R. Araque, “Contributions to the polyhedral approach to vehicle routing,” Ph.D. Thesis, Department of Applied Mathematics and Statistics, SUNY (Stony Brook, 1989).
A. Bachem and M. Grötschel, “New aspects of polyhedral theory,” in: B. Korte, ed.,Modern Applied Mathematics (North-Holland, Amsterdam, 1982) pp. 51–106.
E. Balas, “Notes for the Cornell University Distinguished Lecturer Series,” GSIA, Carnegie-Mellon University (Pittsburg, PA, 1987).
E. Balas and W. Pulleyblank, “The perfectly matchable subgraph polytope of a bipartite graph,”Networks 13 (1983) 495–516.
E. Balas and W. Pulleyblank, “The perfectly matchable subgraph polytope of an arbitrary graph,” Management Science Research Report No. MSRR-538, Carnegie-Mellon University (Pittsburgh, PA, 1987).
E. Burger, “Uber homogene lineare Ungleichungssysteme,”Zeitschrift für Angewandte Mathematik und Mechanik 36 (1956) 135–139.
A. Claus, “A new formulation for the traveling salesman problem,”SIAM Journal of Algebraic Discrete Methods 5 (1984) 21–25.
G. Dantzig, D. Fulkerson and S. Johnson, “Solution of a large-scale traveling-salesman problem,”Operations Research 2 (1954) 393–410.
K. Fox, “Production scheduling on parallel lines with dependencies,” Ph.D. Thesis, Johns Hopkins University (Baltimore, MD, 1973).
K. Fox, B. Gavish and S. Graves, “Ann-constraint formulation of the (time-dependent) traveling salesman problem,”Operations Research 28 (1980) 1018–1021.
D. Gale, “Convex polyhedral cones and linear inequalities,” in: Tj. Koopmans, ed.,Activity Analysis of Production and Allocation (Wiley, New York, 1951) pp. 287–297.
R. Garfinkel, “Motivation and modeling,” in: E. Lawler et al., eds.,The Traveling Salesman Problem (Wiley, New York, 1985) Chapter 2.
M. Gerstenhaber, “Theory of convex polyhedral cones,” in: Tj. Koopmans, ed.,Activity Analysis of Production and Allocation (Wiley, New York, 1951) pp. 298–316.
M. Grötschel and M. Padberg, “Polyhedral theory,” in: E. Lawler et al., eds.,The Traveling Salesman Problem (Wiley, New York, 1985) Chapter 8.
I. Heller, “On the travelling salesman problem,”Proceedings of the Second Symposium on Linear Programming, Washington, D.C., January 29, 1955.
K. Hoffman and M. Padberg, “LP-based combinatorial problem solving,”Annals of Operations Research 4 (1985/6) 145–194.
E. Johnson, “On cut-set integer polyhedra,”Cahiers du Centre de Recherche Operationelle 17 (1974) 235–251.
N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
L.G. Khachiyan, “A polynomial algorithm in linear programming,”Soviet Mathematics Doklady 20 (1979) 191–194.
C. Miller, A. Tucker and R. Zemlin, “Integer programming formulations and traveling salesman problems,”Journal of the Association for Computing Machinery 7 (1960) 326–329.
M. Padberg, “Equivalent knapsack-type formulations of bounded integer linear programs: an alternative approach,”Naval Research Logistics Quarterly 19 (1972) 699–708.
M. Padberg and Ting-Yi Sung, “An analytic symmetrization of max flow—min cut,” Preprint, Stern School of Business, New York University (New York, 1989).
J. Picard and M. Queyranne, “The time-dependent travelling salesman problem and its application to the tardiness problem in one-machine scheduling,”Operations Research 26 (1978) 86–110.
M. Simmonnard,Linear Programming (Prentice-Hall, Englewood Cliffs, NJ, 1966).
J. Stoer and C. Witzgall,Convexity and Optimization in Finite Dimensions I (Springer, Berlin, 1970).
Ting-Yi Sung, “Contributions to the travelling salesman problem and its variants,” Ph.D. Thesis, Stern School of Business, New York University (New York, 1988).
H. Weyl, “Elementare Theorie der konvexen Polyeder,”Commentarii Mathematici Helvetici 7 (1935) 290–306. [Translation in: H. Kuhn and A. Tucker, eds.,Contributions to the Theory of Games I (Princeton University Press, Princeton, NJ, 1950) pp. 3–18.]