help-glpk
[Top][All Lists]

## Re: [Help-glpk] handling symmetries among constraints

 From: Michael Hennebry Subject: Re: [Help-glpk] handling symmetries among constraints Date: Thu, 27 Dec 2007 10:52:01 -0600 (CST)

```On Mon, 24 Dec 2007, Erik Rantapaa wrote:

> 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.

I don't know that there are good ways.
Something like L(A)(x)>=L(B)(x), where L(A) and L(B) are linear
functions related by symmetry, is correct in principle,
but often too loose to be useful.

> 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?

Probably the best is a reformulation in which A and B lose their identities.
Perhaps something that represents paths through time:
x[s,t] = 1 iff s< t and the same person works at times s and t,
but not at times s+1..t-1 .

--