I am attending MIP 2013 in Madison, Wisconsin this week. In honor of mixed integer programming, I am going to blog about one MIP myth every day during the conference. The Myths are from the excellent “Myths and Counterexamples in Math Programming” in the Mathematical Programming Glossary.
Today’s MIP Myth is as follows: If an integer linear program has an unbounded linear programming relaxation, the integer linear program is also unbounded.
The following counterexample is due to Byrd, Goldman, and Heller , which is based on Meyer , who showed this cannot happen with rational data and a feasible integer linear program.
The counterexample uses irrational data. Here is the IP model:
With linear variables, the objective is maximized as . In fact, the LP relaxation contains the ray . Therefore, the LP relaxation is unbounded.
Let’s take a look at this problem with integer variables. The first constraint (rearranged yields ) can only happy when both sides are zero for integer variables. Therefore, we know that or and that in either case. Putting this together, there are only two feasible points in the integer programming model: (0, 0, 0, 1) and (1, 1, 0, 0). As you can see, it is not unbounded.
1. RH Byrd, AJ Goldman, M Heller. (1987). Recognizing unbounded integer programs. Operations Research 35(1), 140-142.
2. RR Meyer (1974). On the existence of optimal solutions to integer and mixed-integer programming problems. Mathematical Programming 7(1), 223-235.
Note: this myth is #13 in the IP chapter.