July 23, 2013

mixed integer programming myth of the day

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 [1987], which is based on Meyer [1974], who showed this cannot happen with rational data and a feasible integer linear program.

The counterexample uses irrational data. Here is the IP model:

$\max x_1 : x \ge 0,\ x \in Z^4,\ x_3 - \sqrt{2} (x_1 - x_2) = 0,\ x_2 + x_4 = 1$

With linear variables, the objective is maximized as $x_1 \rightarrow \infty$ . In fact, the LP relaxation contains the ray $\{(t, 0, t \sqrt{2}, 1) : t \ge 0\}$ . Therefore, the LP relaxation is unbounded.

Let’s take a look at this problem with integer variables. The first constraint (rearranged yields $x_3 = \sqrt{2} (x_1 - x_2)$ ) can only happy when both sides are zero for integer variables. Therefore, we know that $x_1 = x_2 = 0$ or $x_1 = x_2 = 1$ and that $x_3 = 0$ 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.

References:
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.

For more optimization and integer programming tricks, please read Paul Rubin’s blog and Marc-Andre Carle’s blog.

This entry was posted on Tuesday, July 23rd, 2013 at 7:00 am and tagged with math programming, mip and posted in Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.

6 responses to “mixed integer programming myth of the day”

JFPuget
July 23rd, 2013 at 7:39 am

Interesting.

In practice people use floating point MIP solvers. It seems that in this case the myth is true given these floating point numbers are rational numbers.
prubin73
July 23rd, 2013 at 10:40 am

J-F: Does “IS unbounded” equal “LOOKS unbounded”? The distinction may be somewhat pedantic, since the user typically has little choice but to accept what the solver announces. On the other hand, I’ve seen more than one feasible model that solvers reported to be infeasible (often due to numerical stability problems), and in some cases the user was sitting on a known feasible solution. So is a model with a known feasible solution infeasible just because the solver said so?
JFPuget
July 23rd, 2013 at 10:57 am

Paul, I was merely referring to Meyer [1974], who showed this cannot happen with rational data and a feasible integer linear program. A problem that can be input to “standard” MIP solvers is using rational hence will comply with the myth.
That’s theory.
In practice, all the issues you raise can happen.
prubin73
July 23rd, 2013 at 1:09 pm

J-F: I guess I really should have pointed to the difference between the problem you intend to solve and the one you are actually solving (which, due to truncation error, is obviously different and, as you noted, inevitably has rational parameters). Incidentally, I did verify that CPLEX (12.5) considers the Byrd et al. example problem to be unbounded.
Laura McLay
July 23rd, 2013 at 4:54 pm

@JFPuget and @prubin73: This post addressed the theoretical issue. In practice, floating point numbers and numerical stability sometimes introduce unexpected problems. I took a numerical analysis class in my first semester of grad school and loved it. It was helpful later on when solvers and code returned solutions that didn’t make sense. That issue is definitely worth mentioning here with this “myth” – thank you for bringing it up. That will be a blog post for another day. And Paul, thanks for verifying with CPLEX (Very interesting!)
prubin73
July 23rd, 2013 at 5:10 pm

@lauramclay: Coincidentally, I too took numerical analysis my first term of grad school, and have had multiple occasions to be grateful for the experience. (It was also a great stress reliever: it immediately eliminated any pressure to maintain a 4.0 cumulative average. :-)) Summing a series of numbers in ascending order and then in descending order and getting different results is a great way to introduce you to the concept that computers are not to be trusted (although the movie 2001: A Space Odyssey already had me somewhat suspicious of them).

Incidentally, I’ve seen at least one report of a bounded problem that CPLEX declared to be unbounded (and not due to numerical instability) — further proof that the problem you are solving is not the problem you think you are solving.