help-glpk
[Top][All Lists]

## Re: [Help-glpk] Newbie scheduling problem question, contiguous time inte

 From: Michael Hennebry Subject: Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints Date: Fri, 31 May 2013 13:18:49 -0500 (CDT) User-agent: Alpine 1.00 (DEB 882 2007-12-20)

```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.

Swapping Monday-Friday and Tuesday-Thursday would not invalidate a solution.
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.

--