Polyhedral Combinatorics - Facets of 0-1 Polytopes

Facets of 0-1 Polytopes

It is important in the context of cutting-plane methods for integer programming to be able to describe accurately the facets of polytopes that have vertices corresponding to the solutions of combinatorial optimization problems. Often, these problems have solutions that can be described by binary vectors, and the corresponding polytopes have vertex coordinates that are all zero or one.

As an example, consider the Birkhoff polytope, the set of n × n matrices that can be formed from convex combinations of permutation matrices. Equivalently, its vertices can be thought of as describing all perfect matchings in a complete bipartite graph, and a linear optimization problem on this polytope can be interpreted as a bipartite minimum weight perfect matching problem. The Birkhoff–von Neumann theorem states that this polytope can be described by two types of linear inequality or equality. First, for each matrix cell, there is a constraint that this cell has a non-negative value. And second, for each row or column of the matrix, there is a constraint that the sum of the cells in that row or column equal one. The row and column constraints define a linear subspace of dimension n2 − 2n + 1 in which the Birkhoff polytope lies, and the non-negativity constraints define facets of the Birkhoff polytope within that subspace.

However, the Birkhoff polytope is unusual in that a complete description of its facets is available. For many other 0-1 polytopes, there are exponentially many or superexponentially many facets, and only partial descriptions of their facets are available.