mixed integer programming myth of the day: problems vs. models

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

Today’s MIP Myth (#16) is as follows: Alternative optima in a MIP model correspond to equally good problem solutions.

I like this myth because it addresses the difference between the problem and the model. We assume they are the same, but they are not. Additionally, there may be multiple ways to model the same problem.

Consider the TSP (a problem!). Here is one IP for the TSP:

Here, the variables if node j is visited after node i. The c values are the costs/distances. Assume that c is symmetric here. The second line makes sure that each city/node is visited once. The last line shows the subtour elimination constraints.

There are several alternative optima that are not equally good alternative problem solutions; they are the same solutions. Let’s assume that there is a single tour in the problem that optimizes the objective function. Here, notice that with symmetric costs, it doesn’t matter if we traverse this tour forward or backward. In the model, this single optimal solution can be represented by two solutions that have the same objective function value (starting with node 1):

.
with
if and 0 otherwise.

Here is a picture of these two tours.

These two TSP tours are the same solution illustrated forward and backward.

There are other ways to model the TSP. One involves defining the variables as:
if node i is the kth node in the tour and 0 otherwise. Parts of the IP model above would have to be reformulated, but I’ll omit that here. There are n identical solutions (2n if the costs are symmetric). The following two tours are different solutions to the model that are the same tour in the problem:

and so on.

This issue is called symmetry in integer programs, where you can relabel the vertices, rotate the problem, perform a rigid transformation, etc. and have the same solution with a different representation of the variables. It can really slow down solver/algorithm performance, which is why some people work on breaking symmetry.

I liked finding this myth because it’s practical, important to know, and something I haven’t done a good job at conveying to students. I’ll be sure to do a better job in the future.

Comments are welcome!