[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