[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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 .
--
Michael address@hidden
"I AM DEATH, NOT TAXES. *I* TURN UP ONLY ONCE." -- Death