Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints

[Michael Hennebry]

On Fri, 31 May 2013, Roland Roberts wrote:

> On 05/30/2013 09:09 PM, Jeffrey Kantor wrote:
> There are 36 classes, 24 student groups, 26 periods, 5 days. For any given 
> student group, there are only 12 classes open. As an example, for grade 6 
> there are two distinct class offerings for each of the core subjects of math, 
> English, science, and social studies (a standard and advanced class). Any 
> particular student will be in only 4. At present, if you are in the standard 
> math class, you are also in the standard English, science and social studies 
> classes. It seems like that ought to help reduce the number of variables, but 
> I don't see how right now, and our principal would like to relax that, at 
> least in the 8th grade as the city has tasked us with opening the advanced 
> classes to more students.
>
> > Moreover, there may be quite a  bit of symmetry in your solution space 
> > which would need to be addressed for a problem of this scale. Can you 
> > clarify what you mean by solving the problem? For example, is any feasible 
> > solution good enough?  Or is there some specific criterion you trying to 
> > optimize?

You will have a symmetry whenever you can generate a new
solution by renumbering the variables on an old solution.

I expect your problem is symmetric about midweek:
Swapping Monday-Friday and Tuesday-Thursday would not invalidate a solution.
I expect your problem is symmetric about midday:
Reversing the order of periods would not invalidate a solution.
I expect that there are sets of equivalent (class, group) pairs.

To deal with midweek symmetry require
 5
SUM  q[d]*X[d]  >=0,
d=1

where q=[-2, -1, 0, 1, 2]

Midday symmetry could be handled similarly.

Suppose (c1, g1), (c2, g2) and (c3, g3) are equivalent.
Require

SUM q[p,d]*X[c3,g3,p,d] >= SUM q[d,p]*X[c2,g2,p,d] >= SUM q[d,p]*X[c1,g1,p,d]
d,p                        d,p                        d,p

where q is nonzero

> Any feasible solution will work.

Use depth-first.
Pick a real good objective.

--
Michael   address@hidden
"On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword."  --  Lily