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:

\min \sum_{i,j} c_{ij} x_{ij} : x \in \{0,1\}^{n \times n}
\sum_i x_{ij} = 1, \ \forall j,\ \sum_j x_{ij} = 1, \ \forall i
\sum_{(i,j) \in S} x_{ij} \le |S|-1,\ \forall S : \emptyset \neq S \subset \{1,...,n\}

Here, the variables x_{ij}=1 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):

x^* = \{1,2,...,n-1,n,1\}

x' = \{1,n,n-1,...,2,1\}.
with
x'_{ij}=1 if x^*_{ji}=1 and 0 otherwise.

Here is a picture of these two tours.

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

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:
x_{ik} = 1 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:

\{1,2,...,n-1,n\}
\{2,3,...,n-1,n,1\}
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!


One response to “mixed integer programming myth of the day: problems vs. models

  • prubin73

    I think there are at least three distinct views on what to do about symmetry in MIP models: eliminate it from the model (e.g., Sherali & Smith 2001); eliminate it via cuts during branch-and-cut (e.g., Margot 2002); or exploit it during branching (e.g., Ostrowski, Linderoth, Rossi & Smriglio 2011). The constraint programming folks are also painfully aware of symmetry, and have their own ways of dealing with it. I’m not sure if those methods map to the aforementioned.

    As a math major, I find the issue a trifle ironic. In all other areas of mathematics, symmetry is the mathematician’s friend.

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 )

Facebook photo

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

Connecting to %s

%d bloggers like this: