[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [Help-glpk] handling symmetries among constraints

**From**: |
Erik Rantapaa |

**Subject**: |
[Help-glpk] handling symmetries among constraints |

**Date**: |
Mon, 24 Dec 2007 19:39:37 -0800 (PST) |

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

**[Help-glpk] handling symmetries among constraints**,
*Erik Rantapaa* **<=**