A commonly used argument in integer programming goes as follows. Suppose we want to show that inequality does not induce a facet of a polyhedron. If we know valid inequalities (1) and (2) that add up to , then we have shown that cannot induce a facet. Right?

Not quite.

One problem occurs when inequalities (1) and (2) are multiples of . For example, suppose that each inequality is .

What if the inequalities are not multiples of ?

Still no cigar.

Another problem occurs when the polyhedron is not full-dimensional. Consider the set of all such that (meaning that we have an implicit equality constraint ). We want to argue that the inequality does NOT induce a facet. This seems to follow from the valid inequalities and which sum to . However, the inequality DOES induce a facet; the dimension of our feasible region is one, the inequality is valid, and the face where has dimension zero.

Stefano ConiglioThat’s why you should *never* work with not full-dimensional polytopes (or, at least, bring them down to some “canonical” full-dimensional representation)! 😉