Abstract
In polyhedral combinatorics one often has to analyze the facial structure of less than full dimensional polyhedra. The presence of implicit or explicit equations in the linear system defining such a polyhedron leads to technical difficulties when analyzing its facial structure. It is therefore customary to approach the study of such a polytopeP through the study of one of its (full dimensional) relaxations (monotonizations) known as the submissive and the dominant ofP. Finding sufficient conditions for an inequality that induces a facet of the submissive or the dominant of a polyhedron to also induce a facet of the polyhedron itself has been posed in the literature as an important research problem. Our paper goes a long way towards solving this problem. We address the problem in the framework of a generalized monotonization of a polyhedronP, g-mon(P), that subsumes both the submissive and the dominant, and give a sufficient condition for an inequality that defines a facet of g-mon(P) to define a facet ofP. For the important cases of the traveling salesman (TS) polytope in both its symmetric and asymmetric variants, and of the linear ordering polytope, we give sufficient conditions trivially easy to verify, for a facet of the monotone completion to define a facet of the original polytope itself.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Balas, The asymmetric assignment problem and some new facets of the traveling salesman polytope on a directed graph,SIAM Journal on Discrete Mathematics 2 (1989) 425–451.
E. Balas, Finding out whether a valid inequality is facet defining, in: R. Kannan and W.R. Pulleyblank, eds.,Integer Programming and Combinatorial Optimization (University of Waterloo Press, 1990) 45–61.
E. Balas and M. Fischetti, The fixed-outdegree 1-arborescence polytope,Mathematics of Operations Research 17 (1992) 1001–1018.
E. Balas and M. Fischetti, A lifting procedure for the asymmetric traveling salesman polytope and a large class of new facets,Mathematical Programming 58 (1993) 325–352.
S.C. Boyd and W.R. Pulleyblank, Facet generating techniques, Department of Combinatorics and Optimization, University of Waterloo, 1991.
S. Chopra and G. Rinaldi, The graphical asymmetric traveling salesman polyhedron, in: R. Kannan and W.R. Pulleyblank, eds.,Integer Programming and Combinatorial Optimization (University of Waterloo Press, 1990).
W. Cunningham and J. Green-Krotki, Dominants and submissives of matching polyhedra,Mathematical Programming 36 (1986) 228–237.
M. Fischetti, Facets of the asymmetric traveling salesman polytope,Mathematics of Operations Research 16 (1991) 42–56.
M. Fischetti, Three facet lifting theorems for the asymmetric traveling salesman polytope, in: E. Balas, G. Cornuejols and R. Kannan, eds.,Integer Programming and Combinatorial Optimization (Proceedings of IPCO 2), GSIA, Carnegie Mellon University (1992) 260–273.
M. Grötschel,Polyedrische Charakterisierungen Kombinatorischer Optimierungsprobleme (Hain, Maisenheim am Glen, 1977).
M. Grötschel, M. Jünger and G. Reinelt, On the acyclic subgraph polytope,Mathematical Programming 33 (1985) 28–42.
M. Grötschel, M. Jünger and G. Reinelt, Facets of the linear ordering polytope,Mathematical Programming 33 (1985) 43–60.
M. Grötschel and M. Padberg, Polyhedral theory, in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D. Shmoys, eds.,The Traveling Salesman Problem (Wiley, New York, 1985) 251–305.
M. Grötschel and W.R. Pulleyblank, Clique tree inequalities and the symmetric traveling salesman problem,Mathematics of Operations Research 11 (1986) 537–569.
F. Margot, Composition de polytopes combinatoires: Une approche par projection, Thèse de doctorat No. 1209, EPF Lausanne, Switzerland, 1994.
D. Naddef and G. Rinaldi, The graphical relaxation: A new framework for the symmetric traveling salesman polytope,Mathematical Programming 58 (1993) 53–87.
G.L. Nemhauser and L. Wolsey,Integer and Combinatorial Optimization (Wiley, New York, 1988).
M. Queyranne and Y. Wang, Hamilton path and symmetric travelling salesman polytopes, Working Paper 89-MSc-009, University of British Columbia, Vancouver, 1989.
M. Queyranne and Y. Wang, Symmetric inequalities and their composition for asymmetric travelling salesman polytopes, 1994; Submitted toMathematical Programming.
G. Rinaldi and L.A. Wolsey,Integer Programming and Combinatorial Optimization (Proceedings of IPCO 3), CORE, Louvain-la-Neuve, Belgium, 1993.
Author information
Authors and Affiliations
Additional information
Research supported by grant DMI-9201340 of the National Science Foundation and contract N00014-89-J-1063 of the Office of Naval Research.
Research supported by MURST, Italy.
Rights and permissions
About this article
Cite this article
Balas, E., Fischetti, M. On the monotonization of polyhedra. Mathematical Programming 78, 59–84 (1996). https://doi.org/10.1007/BF02614506
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02614506