Punk Rock Operations Research

• Punk Rock OR Tweets

• I can't believe how many students arrived late to an 8am final. Latecomers missed my pre-exam pep talk. 13 minutes ago
• I am giving my final exam in less than 10 hrs. I am officially calling it a night - no more answering student questions. I can't oversleep! 10 hours ago
• Study: Teachers give better grades to more attractive students healthland.time.com/2013/12/10/tea… This is why I grade exams without looking at names. 11 hours ago
• I can hear my voice echo back from another line on a conference call. Yikes, I didn't realize my Chicago accent came back with a vengeance. 17 hours ago
• That moment when you notice a spelling error on an exam question right after you've finished printing your final exams #Crap 17 hours ago
• I spelled "Chebyshev" correctly on the first time. I still can't get "accommodate" correctly without the aid of a spellchecker. 17 hours ago
• Student suggested that my stochastic processes course needs another prereq: students should be familiar with Star Wars episodes IV-VI. 17 hours ago
• On busy days like today, this is my email triage & response strategy: phdcomics.com/comics/archive… ...but I'm not averaging 1.3 sec per response. 23 hours ago

mixed integer programming myth of the day: checking for feasibility

Posted by Laura McLay on July 25, 2013

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:

$\max x_1 :\ x \in \{0,1\}^n,\ 2 x_1 + 2 x_2 + ... + 2 x_n = n.$

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 $2^{\lceil n/2 \rceil}$ 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.