[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

reply via email to

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