mixed integer programming myth of the day: checking for feasibility

This is the third post in my MIP 2013 series on mixed integer programming myths and counterexamples. See my first two posts here and here. Again, the Myths are from the excellent “Myths and Counterexamples in Math Programming”  in the Mathematical Programming Glossary.

Today’s MIP Myth (#22) is as follows: For any 0-1 integer program with a single constraint, there is a branch-and-bound algorithm that can determine if the 0-1 integer program has a feasible solution in polynomial time.

Read about branch-and-bound (B&B) here. The idea is that a linear programming model is solved, and if the solution has variables with fractional values, a tree is created that branches on one of the fractional variables. For binary variables considered here, one branch would set the variable in question to 0 and the other branch would set the variable equal to 1. In the worst case, the tree has depth n, where n is the number of variables, which leads to a tree with an exponential number of nodes.

The myth here explores whether it is possible to quickly check to see if the integer program admits any feasible solution up front. Quick here means in polynomial time. This can be achieved without having to create the entire B&B tree with its exponential size. To show that checking for feasibility sometimes requires exponential time, consider the following IP:

From inspection, we can see that there no feasible solutions if n is odd. If n is even, there are many feasible solutions. (Note: there is a lot of symmetry in this IP).

Jeroslow (1974) shows that for any fixed values of the fractional variables in the linear programming relaxation, one must evaluate at least nodes before it certifies that it is infeasible (not polynomial time). The paper is very short and provides the proof (see the reference below).

The following note was in the “Myths and Counterexamples in Math Programming”:

Ed Klotz points out that modern B&B algorithms are more broadly construed to include preprocessing, among other things, that would solve this example without exhaustive search. The counterexample does emphasize the need for such things.

Reference:
RG Jeroslow, 1974. Trivial integer programs unsolvable by branch-and-bound, Mathematical Programming 6(1), 105-109.