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?
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.