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.

Advertisements

6 responses to “mixed integer programming myth of the day

  • JFPuget

    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

    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

    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

    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

    @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

    @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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: