# A fallacious argument in integer programming

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

Not quite.

One problem occurs when inequalities (1) and (2) are multiples of $ax\le b$. For example, suppose that each inequality is $(ax)/2 \le b/2$.

What if the inequalities are not multiples of $ax \le b$?

Still no cigar.

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

## One thought on “A fallacious argument in integer programming”

1. Stefano Coniglio

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