On the monotonization of polyhedra
Balas, Egon
Fischetti, Matteo

Data: 1997
Resum: 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 polytope P through the study of one of its (full dimensional) relaxations (monotonizations) known as the submissive and the dominant of P. 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 polyhedron P, 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 of P. 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. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Matèria: Polyhedral combinatorics ; Monotone polyhedra ; Submissive ; Dominant
Publicat a: Mathematical Programming, vol. 78 n. 1 (1997) p. 59-84, ISSN 0025-5610

26 p, 1.3 MB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03

   Favorit i Compartir