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 [EMAIL PROTECTED]
"I AM DEATH, NOT TAXES. *I* TURN UP ONLY ONCE." -- Death
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
