logo_acta

Acta Mathematica Vietnamica

RECOGNIZING FACET DEFINING INEQUALITIES

icon-email E. BALAS

Abstract

We discuss a method for determining whether a valid inequality for a 0-1 polytope is facet defining. The method is based on a
new procedure for generating a sequence of 0-1 points on a face of the polytope, guaranteed to be linearly independent. The sequence moves along $k$-dimensional surfaces of the face, and whenever this is possible for small $k$, the procedure becomes particularly simple. As a result, we give a new sufficient condition for a valid inequality to be facet defining, that generalizes several earlier conditions. We also give a necessary and sufficient condition. None of these conditions is always verifiable in polynomial time. yet in many situations their use has led to the discovery of new classes of facets. We illustrate this on the case of the vertex packing and set covering polyhedra.