Hi Roland, Before going into some thoughts regarding the modeling aspects, could you tell us about the scale of your problem? For example, if there are, say, 20 classes, 10 student groups, 26 periods, and 5 days, then you have 20*10*26*5 = 26,000 binary variables in your assignment formulation. That's a pretty large number.
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? As a suggestion, developing solutions to problems like this can be pretty challenging. So it might make sense to look at some simplified cases and special cases, and perhaps test some problem specific heuristics. Jeff On Thu, May 30, 2013 at 11:14 AM, Michael Hennebry < [email protected]> wrote: > On Wed, 29 May 2013, Roland Roberts wrote: > > On 05/29/2013 01:27 PM, Michael Hennebry wrote: >> >>> On Tue, 28 May 2013, Roland Roberts wrote: >>> >>> The basic problem is that I classes c, student groups g, time periods >>>> p, and days d. We're breaking each day into 15-minute "modules" which have >>>> to be schedule. A class has to span 3-8 modules on any give day. Some >>>> classes have a minimum number of modules per week that have to be >>>> completed. With just the above, I can specify the constraints by thinking >>>> of this as a 4-dimensional array X[c,g,p,d] and the constraints are various >>>> sums. The problem I run into is specifying the the continuity constraint on >>>> scheduling. It's not sufficient to have 3 modules for class C1, they have >>>> to be 3 contiguous modules. >>>> >>>> How do I specify this sort of thing? >>>> >>> >>> Is each class a fixed length? >>> >> >> No, that's the first thing the school wants to relax with the modular >> > > My previous constraints were necessary, but not sufficient. > They would allow breaking the day into 3 or > more parts with middle parts being too short. > > The following are sufficient > to ensure all blocks have at least 4 periods: > > X[c,g,p1,d]-X[c,g,p2,d]+X[c,g,**p3,d]>=0 for p1< p2< p3<=p1+4, c,g,d... > > where periods outside of a day are implictly 0. > > Note that the constraints are numerous (quadratic > in the size of a minimum block) and rather loose. > > > -- > Michael [email protected] > "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 > > ______________________________**_________________ > Help-glpk mailing list > [email protected] > https://lists.gnu.org/mailman/**listinfo/help-glpk<https://lists.gnu.org/mailman/listinfo/help-glpk> >
_______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
