On the monotonization of polyhedra
Balas, Egon
Fischetti, Matteo

Fecha: 1997
Resumen: 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. .
Derechos: Tots els drets reservats.
Lengua: Anglès
Documento: Article ; recerca ; Versió publicada
Materia: Polyhedral combinatorics ; Monotone polyhedra ; Submissive ; Dominant
Publicado en: Mathematical Programming, vol. 78 n. 1 (1997) p. 59-84, ISSN 0025-5610



26 p, 1.3 MB
 Acceso restringido a la UAB

El registro aparece en las colecciones:
Artículos > Artículos de investigación
Artículos > Artículos publicados

 Registro creado el 2006-03-13, última modificación el 2023-06-03



   Favorit i Compartir