ON THE MONOTONIZATION OF POLYHEDRA

In polyhedral combinatorics one often has to analyze the facial struct ure 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. I t is therefore customary to approach the study of such a polytope P th rough the study of one of its (full dimensional) relaxations (monotoni zations) known as the submissive and the dominant of P. Finding suffic ient conditions for an inequality that induces a facet of the submissi ve or the dominant of a polyhedron to also induce a facet of the polyh edron itself has been posed in the literature as an important research problem. Our paper goes a long way towards solving this problem. We a ddress the problem in the framework of a generalized monotonization of a polyhedron P, g-mon(P), that subsumes both the submissive and the d ominant, and give a sufficient condition for an inequality that define s 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 asym metric variants, and of the linear ordering polytope, we give sufficie nt conditions trivially easy to verify, for a facet of the monotone co mpletion to define a facet of the original polytope itself. (C) 1997 T he Mathematical Programming Society, Inc. Published by Elsevier Scienc e B.V.