[Help-glpk] handling symmetries among constraints

[Erik Rantapaa]

Merry Xmas everyone!

I was wondering if there are standard techniques for adding constraints to 
break variable symmetries. I am primarily interested in the case where all the 
variables are binary integer variables. I suppose there are a lot of questions 
one could ask in this vein, such as:

1. What is the standard way to define and designate that sets of variables are 
interchangeable with each other (i.e. a rigorous definition)?

2. Given that you have identified a set of symmetries, what are good ways to 
add constraints to help the solver avoid investigating symmetric solution paths.

3. To what extent can the symmetries be found algorithmically?

4. Would it help a solver such as GLPK to know that the problem has certain 
symmetries?

As an example, in a scheduling problem one generally has the following setup:

set Person := {A, B, C, ...};
set Time := 1..N;
var x{Person, Time}, binary; # x[p,t] = 1 iff person p is working at time t

and there are constraints like total work of person p must be between such and 
such, p cannot work at specific times and there must be at least so many people 
working at each time, etc.

If A and B have exactly the same constraints on them, what would be a good way 
to break that symmetry so that solutions are found faster?



      
____________________________________________________________________________________
Be a better friend, newshound, and 
know-it-all with Yahoo! Mobile.  Try it now.  
http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ