[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 

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.;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ 

reply via email to

[Prev in Thread] Current Thread [Next in Thread]