Skip to main content
Top

2013 | OriginalPaper | Chapter

Facets and Rank of Integer Polyhedra

Author : Manfred W. Padberg

Published in: Facets of Combinatorial Optimization

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We discuss several methods of determining all facets of “small” polytopes and polyhedra and give several criteria for classifying the facets into different facet types, so as to bring order into the multitude of facets as, e.g., produced by the application of the double description algorithm (DDA). Among the forms that we consider are the normal, irreducible and minimum support representations of facets. We study symmetries of vertex and edge figures under permissible permutations that leave the underlying polyhedron unchanged with the aim of reducing the numerical effort to find all facets efficiently. Then we introduce a new notion of the rank of facets and integer polyhedra. In the last section, we present old and new results on the facets of the symmetric traveling salesman polytope \(\mathcal{Q}_{T}^{n}\) with up to n=10 cities based on our computer calculations and state a conjecture that, in the notion of rank ρ(P) introduced here, asserts \(\rho(\mathcal{Q}_{T}^{n}) = n - 5\) for all n≥5. This conjecture is supported by our calculations up to n=9 and, possibly, n=10.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
2.
go back to reference Bartels, H.G., Bartels, S.G.: The facets of the asymmetric 5-city traveling salesman problem. ZOR, Z. Oper.-Res. 33, 193–197 (1989) MathSciNetMATH Bartels, H.G., Bartels, S.G.: The facets of the asymmetric 5-city traveling salesman problem. ZOR, Z. Oper.-Res. 33, 193–197 (1989) MathSciNetMATH
5.
go back to reference Christof, T.: Low-dimensional 0/1 polytopes and branch-and-cut in combinatorial optimization. Ph.D. thesis, University of Heidelberg, Heidelberg, Germany (1997) Christof, T.: Low-dimensional 0/1 polytopes and branch-and-cut in combinatorial optimization. Ph.D. thesis, University of Heidelberg, Heidelberg, Germany (1997)
7.
go back to reference Christof, T., Reinelt, G.: Algorithmic aspects of using small instance relaxations in parallel branch-and-cut. Algorithmica 30, 597–629 (2001) MathSciNetMATHCrossRef Christof, T., Reinelt, G.: Algorithmic aspects of using small instance relaxations in parallel branch-and-cut. Algorithmica 30, 597–629 (2001) MathSciNetMATHCrossRef
8.
go back to reference Christof, T., Reinelt, G.: Decomposition and parallelization techniques for enumerating the facets of 0/1 polytopes. Int. J. Comput. Geom. Appl. 11, 423–437 (2001) MathSciNetMATHCrossRef Christof, T., Reinelt, G.: Decomposition and parallelization techniques for enumerating the facets of 0/1 polytopes. Int. J. Comput. Geom. Appl. 11, 423–437 (2001) MathSciNetMATHCrossRef
9.
go back to reference Christof, T., Jünger, M., Reinelt, G.: A complete description of the traveling salesman polytope on 8 nodes. Oper. Res. Lett. 10, 497–500 (2001) CrossRef Christof, T., Jünger, M., Reinelt, G.: A complete description of the traveling salesman polytope on 8 nodes. Oper. Res. Lett. 10, 497–500 (2001) CrossRef
11.
go back to reference Dantzig, G.B., Fulkerson, D.R., Johnson, S.M.: Solution of a large-scale travelling salesman problem. Oper. Res. 2, 393–410 (1954) MathSciNetCrossRef Dantzig, G.B., Fulkerson, D.R., Johnson, S.M.: Solution of a large-scale travelling salesman problem. Oper. Res. 2, 393–410 (1954) MathSciNetCrossRef
12.
go back to reference Deza, M., Grötschel, M., Laurent, M.: Complete descriptions of small multicut polytopes. In: Applied Geometry and Discrete Mathematics, pp. 221–252. Am. Math. Soc., Providence (1991) Deza, M., Grötschel, M., Laurent, M.: Complete descriptions of small multicut polytopes. In: Applied Geometry and Discrete Mathematics, pp. 221–252. Am. Math. Soc., Providence (1991)
13.
go back to reference Edmonds, J.: Maximum matching and a polyhedron with 0–1 vertices. J. Res. Natl. Bur. Stand. B, Math. Math. Phys. 69, 67–92 (1965) MathSciNetMATHCrossRef Edmonds, J.: Maximum matching and a polyhedron with 0–1 vertices. J. Res. Natl. Bur. Stand. B, Math. Math. Phys. 69, 67–92 (1965) MathSciNetMATHCrossRef
14.
go back to reference Euler, R., Verge, H.L.: A complete and irredundant linear description of the asymmetric traveling salesman polytope on 6 nodes. Discrete Appl. Math. 62, 193–208 (1995) MathSciNetMATHCrossRef Euler, R., Verge, H.L.: A complete and irredundant linear description of the asymmetric traveling salesman polytope on 6 nodes. Discrete Appl. Math. 62, 193–208 (1995) MathSciNetMATHCrossRef
15.
go back to reference Fleischmann, B.: Duale und primale Schnitthyperebenenverfahren in der ganzzahligen linearen Optimierung. Ph.D. thesis, University of Hamburg, Hamburg, Germany (1970) Fleischmann, B.: Duale und primale Schnitthyperebenenverfahren in der ganzzahligen linearen Optimierung. Ph.D. thesis, University of Hamburg, Hamburg, Germany (1970)
16.
go back to reference Gomory, R.: An algorithm for integer solutions to linear programs. In: Graves, R.L., Wolfe, P. (eds.) Recent Advances in Mathematical Programming, pp. 269–302. McGraw-Hill, New York (1963) Gomory, R.: An algorithm for integer solutions to linear programs. In: Graves, R.L., Wolfe, P. (eds.) Recent Advances in Mathematical Programming, pp. 269–302. McGraw-Hill, New York (1963)
17.
go back to reference Grötschel, M., Padberg, M.W.: Zur Oberflächenstruktur des Travelling Salesman Polytopen. In: Zimmermann, H.J., Schub, A., Späth, H., Stoer, J. (eds.) Proc. in Operations Research, vol. 4, pp. 207–211. Physica-Verlag, Würzburg (1974) Grötschel, M., Padberg, M.W.: Zur Oberflächenstruktur des Travelling Salesman Polytopen. In: Zimmermann, H.J., Schub, A., Späth, H., Stoer, J. (eds.) Proc. in Operations Research, vol. 4, pp. 207–211. Physica-Verlag, Würzburg (1974)
18.
go back to reference Grötschel, M., Padberg, M.W.: On the symmetric traveling salesman problem. Technical report 7536, OR—Inst. f. Ökonometrie und Operations Research, Bonn, Germany (1975) Grötschel, M., Padberg, M.W.: On the symmetric traveling salesman problem. Technical report 7536, OR—Inst. f. Ökonometrie und Operations Research, Bonn, Germany (1975)
19.
go back to reference Grötschel, M., Padberg, M.W.: On the symmetric traveling salesman problem: parts I and II. Math. Program. 16, 265–302 (1979) MATHCrossRef Grötschel, M., Padberg, M.W.: On the symmetric traveling salesman problem: parts I and II. Math. Program. 16, 265–302 (1979) MATHCrossRef
20.
go back to reference Grötschel, M., Padberg, M.W.: Polyhedral theory. In: Lawler, E.L., Lenstra, J.K., Rinnoy Kan, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985) Grötschel, M., Padberg, M.W.: Polyhedral theory. In: Lawler, E.L., Lenstra, J.K., Rinnoy Kan, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)
21.
go back to reference Grötschel, M., Jünger, M., Reinelt, G.: Facets of the linear ordering polytope. Math. Program. 33, 43–60 (1985) MATHCrossRef Grötschel, M., Jünger, M., Reinelt, G.: Facets of the linear ordering polytope. Math. Program. 33, 43–60 (1985) MATHCrossRef
22.
23.
go back to reference Heller, I.: On the problem of shortest paths between points. Bull. Am. Math. Soc. 59, 551–552 (1953) Heller, I.: On the problem of shortest paths between points. Bull. Am. Math. Soc. 59, 551–552 (1953)
24.
go back to reference Jünger, M., Reinelt, G., Rinaldi, G.: The traveling salesman problem. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds.) Network Models. Handbooks in Operations Research and Management Science, vol. 7, pp. 225–330. North-Holland, Amsterdam (1995) CrossRef Jünger, M., Reinelt, G., Rinaldi, G.: The traveling salesman problem. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds.) Network Models. Handbooks in Operations Research and Management Science, vol. 7, pp. 225–330. North-Holland, Amsterdam (1995) CrossRef
25.
go back to reference Kaibel, V.: Polyhedral combinatorics of the quadratic assignment problem. Ph.D. thesis, University of Cologne, Cologne, Germany (1997) Kaibel, V.: Polyhedral combinatorics of the quadratic assignment problem. Ph.D. thesis, University of Cologne, Cologne, Germany (1997)
26.
go back to reference Kuhn, H.: On certain convex polyhedra. Bull. Am. Math. Soc. 61, 557–558 (1955) Kuhn, H.: On certain convex polyhedra. Bull. Am. Math. Soc. 61, 557–558 (1955)
27.
go back to reference Kuhn, H.: On asymmetric traveling salesman polytopes. Presented at the 14th Intern. Symp. on Mathematical Programming (1991) Kuhn, H.: On asymmetric traveling salesman polytopes. Presented at the 14th Intern. Symp. on Mathematical Programming (1991)
28.
go back to reference Naddef, D., Rinaldi, G.: The crown inequalities for the symmetric traveling salesman polytope. Math. Oper. Res. 17, 308–326 (1992) MathSciNetMATHCrossRef Naddef, D., Rinaldi, G.: The crown inequalities for the symmetric traveling salesman polytope. Math. Oper. Res. 17, 308–326 (1992) MathSciNetMATHCrossRef
29.
go back to reference Naddef, D., Rinaldi, G.: The graphical relaxation: a new framework for the symmetric traveling salesman polytope. Math. Program. 58, 53–88 (1993) MathSciNetMATHCrossRef Naddef, D., Rinaldi, G.: The graphical relaxation: a new framework for the symmetric traveling salesman polytope. Math. Program. 58, 53–88 (1993) MathSciNetMATHCrossRef
30.
go back to reference Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988) MATH Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988) MATH
31.
go back to reference Norman, R.: On the convex polyhedra of the symmetric traveling salesman problem. Bull. Am. Math. Soc. 61, 559 (1955) Norman, R.: On the convex polyhedra of the symmetric traveling salesman problem. Bull. Am. Math. Soc. 61, 559 (1955)
32.
go back to reference Padberg, M.W.: Essays in integer programming. Ph.D. thesis, Carnegie-Mellon University, Pittsburgh, PA (1971) Padberg, M.W.: Essays in integer programming. Ph.D. thesis, Carnegie-Mellon University, Pittsburgh, PA (1971)
37.
39.
go back to reference Padberg, M.W.: Classical cuts for mixed-integer programming and branch-and-cut. Math. Methods Oper. Res. 53, 173–203 (2001). Reprinted in Ann. Oper. Res. 139, 321–352 (2005) MathSciNetMATHCrossRef Padberg, M.W.: Classical cuts for mixed-integer programming and branch-and-cut. Math. Methods Oper. Res. 53, 173–203 (2001). Reprinted in Ann. Oper. Res. 139, 321–352 (2005) MathSciNetMATHCrossRef
41.
go back to reference Padberg, M.W., Hong, S.: On the symmetric traveling salesman problem: a computational study. Math. Program. 12, 78–107 (1980) MathSciNetMATH Padberg, M.W., Hong, S.: On the symmetric traveling salesman problem: a computational study. Math. Program. 12, 78–107 (1980) MathSciNetMATH
42.
go back to reference Padberg, M.W., Rao, M.: The traveling salesman problem and a class of polyhedra of diameter two. Math. Program. 7, 32–45 (1980) MathSciNetCrossRef Padberg, M.W., Rao, M.: The traveling salesman problem and a class of polyhedra of diameter two. Math. Program. 7, 32–45 (1980) MathSciNetCrossRef
43.
go back to reference Padberg, M.W., Rijal, M.: Location, Scheduling, Design and Integer Programming. Kluwer Academic, Boston (1996) MATHCrossRef Padberg, M.W., Rijal, M.: Location, Scheduling, Design and Integer Programming. Kluwer Academic, Boston (1996) MATHCrossRef
44.
go back to reference Padberg, M.W., Sung, T.: A polynomial-time solution to Papadimitriou and Steiglitz’s “traps”. Oper. Res. Lett. 7, 117–125 (1988) MathSciNetMATHCrossRef Padberg, M.W., Sung, T.: A polynomial-time solution to Papadimitriou and Steiglitz’s “traps”. Oper. Res. Lett. 7, 117–125 (1988) MathSciNetMATHCrossRef
45.
go back to reference Papadimitriou, C.H.: The adjacency relation on the traveling salesman polytope is NP-complete. Math. Program. 14, 312–324 (1978) MathSciNetMATHCrossRef Papadimitriou, C.H.: The adjacency relation on the traveling salesman polytope is NP-complete. Math. Program. 14, 312–324 (1978) MathSciNetMATHCrossRef
46.
47.
go back to reference Rispoli, F., Cosares, S.: A bound of 4 for the diameter of the symmetric traveling salesman polytope. SIAM J. Appl. Math. 11, 373–380 (1998) MathSciNetMATH Rispoli, F., Cosares, S.: A bound of 4 for the diameter of the symmetric traveling salesman polytope. SIAM J. Appl. Math. 11, 373–380 (1998) MathSciNetMATH
48.
go back to reference Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986) MATH Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986) MATH
49.
go back to reference Sierksma, G., Tijssen, G.: Faces with large diameter on the symmetric traveling salesman polytope. Oper. Res. Lett. 12, 73–77 (1992) MathSciNetMATHCrossRef Sierksma, G., Tijssen, G.: Faces with large diameter on the symmetric traveling salesman polytope. Oper. Res. Lett. 12, 73–77 (1992) MathSciNetMATHCrossRef
Metadata
Title
Facets and Rank of Integer Polyhedra
Author
Manfred W. Padberg
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-38189-8_2