Symmetry and The Quest for All Solutions

This is an addendum to Wednesday's post on finding all solutions to linear and (mixed) integer linear programs.

In the context of integer programming models, symmetry refers to situations in which some nontrivial permutation of the indices of variables (and perhaps constraints)  yields the original problem again. The implication is that, given a feasible solution to the problem, applying an appropriate permutation to the variables results in another, nominally distinct, feasible solution with identical objective value. I don't intend to go into symmetry in depth here, but in general terms the implication is that, left untreated, symmetry can slow the progress of branch-and-bound or branch-and-cut algorithms. The reason is that when incumbent solutions are found, the existence of their symmetric counterparts in other portions of the tree (with identical objective value) inhibits pruning of nodes based on bounds.

[Edit: I've added a fourth approach. Hat tip to Ed Klotz for reminding me of it in a comment.]

There are three four fundamental approaches to dealing with symmetry:

• eliminate it in the model by adding constraints;
• modify the algorithm to take it into account;
• do nothing and live with the slower convergence of the algorithm; or
• find an alternative model with no (or less) symmetry.

The purpose of this post is to point out that, when looking for all or even several optimal solutions to integer problems, the last option is a poor choice.

A quick example

Packing and covering problems are notorious for symmetry, so I'll use a packing problem as an example. Suppose that I am moving my household, using a moving company. The moving company provides boxes, which I will charitably assume are identical in size and shape. They also charge for the boxes, so I wish to use the fewest boxes possible. Being an OR person, I create and solve a bin packing model. The optimal solution puts my gym clothes and my paperback books in box #3 and my fine china and my computer in box #7. (I never said it was a good model.)

Now suppose I (carefully) dump out the contents of boxes 3 and 7 and swap them, packing the china and computer in box #3 and gym clothes and paperbacks in box #7. The boxes are identical, so everything fits. I have not changed the number of boxes being used (the objective function), so this second solution is again optimal.

But is it really a "second solution"? The numbering of the boxes means nothing to me. When I get to my destination, the one making all the clattering sounds will have the computer and what's left of the china, and the one smelling a bit ripe will have the paperback books and the gym clothes (did I mention I forgot to wash them?), regardless of the numbers printed on them.

The reformulation option

 

As Ed Klotz notes in his comment, sometimes a different formulation eliminates the symmetry, possibly (but not necessarily) at the expense of adding variables. For example, I recently was playing with a vehicle routing problem (VRP) in which the vehicles are all identical. The VRP requires assigning customers to vehicles and then organizing each vehicles route (essential a traveling salesman problem for each vehicle). A straight-up formulation might look like the following (in which $d_{ij}$ is the distance or travel cost between customers $i$ and $j$, with $i=0$ for the depot, $c_i$ is the load required by customer $i\in\{1,\dots,N\}$, and $C$ is the capacity of each of the $V$ vehicles:
\[ \begin{array}[t]{lrclr} \mathrm{minimize} & & \sum_{v=1}^{V} \sum_{i=0}^{N}\sum_{j=0}^{N} d_{ij}x_{ijv}\\ \mathrm{s.t.} & \sum_{v=1}^{N}y_{iv} & = & 1 & \forall i>0\\ & \sum_{i=0}^{N}x_{ijv} & = & y_{jv} & \forall j>0,\forall v\\ & \sum_{i=0}^{N}x_{jiv} & = & y_{jv} & \forall j>0,\forall v\\ & \sum_{j=1}^{N}c_{j}y_{jv} & \le & C & \forall v\\ & x_{ijv},y_{iv} & \in & \left\{ 0,1\right\} & \forall i,j>0,\forall v\\ & ? & ? & ? \end{array} \]Binary variables $x_{ijv}$ signal whether stop $j$ (a customer or, if $j=0$, the depot) immediately follows stop $i$ on the route for vehicle $v$, while the binary variables $y_{iv}$ signal whether customer $i$ is assigned to vehicle $v$. The first constraint requires that every customer be assigned to exactly one vehicle. The second and third say that, on any given route, a particular customer is entered and exited exactly once if on that route and zero times if not. The fourth constraint asserts the capacity limit of the vehicles. The final set of constraints (which I deliberately omitted -- the question marks) would be subtour elimination constraints, which can be handled in a variety of ways.

The fact that all vehicles are identical introduces one level of symmetry: if I take a feasible (optimal) solution and rotate the routes among the vehicles, I get an equivalent feasible (optimal) solution. Another source of symmetry is that, within any single route, if I traverse the route in reverse order I get another solution with an identical objective value.

The indistinguishable nature of the vehicles, though, allows us to rethink the formulation in a way that both eliminates the first level of symmetry and also reduces the size of the model. Suppose that, instead of having $V$ vehicles, I had one vehicle that would be making $V$ runs, returning to the "barn" each time. The total number of stops in a day would be $N+V+1$, consisting of starting the day at the depot (1), stopping at each customer ($N$), and returning to the depot $V$ times. So we can think of the entire day's schedule as a single string of integers $0,\dots,N$ with $V+1$ zeros and one instance of each other integer.

With that picture in mind, let $x_{ij}$ be 1 if stop $j$ immediately follows stop $i$ in the master schedule for the day, and let $u_i$ be the load of the vehicle when arriving at stop $i\ge 0$. Assume that $c_0=0$ (the depot has no demand). We arrive at the following alternative model:
\[ \begin{array}[t]{lrclr} \mathrm{minimize} & & \sum_{i=0}^{N}\sum_{j=0}^{N} & d_{ij}x_{ij}\\ \mathrm{s.t.} & \sum_{i=0}^{N}x_{ij} & = & \begin{cases} 1 & j>0\\ V & j=0 \end{cases} & \forall j\ge0\\ & \sum_{i=0}^{N}x_{ji} & = & \begin{cases} 1 & j>0\\ V & j=0 \end{cases} & \forall j\ge0\\ & u_{j}-u_{i} & \le & C-\left(C+c_{i}\right)x_{ij} & \forall i>0,\forall j\ge0\\ & x_{ij} & \in & \left\{ 0,1\right\} & \forall i,j\ge0\\ & u_{j} & \in & [0,C] & \forall j\ge0 \end{array} \] The first two constraints say that every customer is entered and exited once, while the depot is entered and exited exactly once per route. (If the depot occurs in two consecutive stops, it means we have more vehicles than we need.) The third constraint says that the load in the vehicle when entering stop $j$ is no greater than the load entering the previous stop minus the demand at that stop, with the important exception that at the first stop after a trip to the depot, the limit is not enforced (so the maximum load entering the first post-depot stop is $C$, the vehicle capacity).

The model still contains the second source of symmetry -- if we reverse the stops between any two consecutive visits to the depot, the travel distance is unchanged -- but we have eliminated the first source of symmetry. Once we have a solution, we can use a random number generator (or take bribes from the drivers) to assign routes to vehicles.

The reason to find "all" solutions

As I mentioned in the previous post, possible motivations for finding all (or at least multiple) optimal solutions include providing decision makers with choices and dealing with secondary criteria omitted from the model. In either of those cases, I'm fairly certain that providing solutions that are permutations of the original solutions will be unsatisfactory. To quote Spock (in the novel "Spock Must Die!"), "a difference which makes no difference is no difference". So in those cases it behooves you to avoid solutions that are permutations of other solutions. If you take the third approach ("do nothing"), not only will solution time increase, but you will need to screen solutions to detect which are permutations.

If permutations will do ...

On the other hand, if permuted solutions satisfy your lust for multiple solutions, I would still advocate either constraining the symmetry away or modifying the algorithm to avoid (or exploit) it where possible. Doing either of those requires that you recognize the symmetry (which is often something as simple as permuting labels of things). Once you find a proven optimal solution, it is quick and easy to manually apply the permutation(s) to find other "distinct" optima.