constraint programming for academic timetabling

[J. Friedman]

For the last year I have been working on an academic timetabling algorithm to schedule classes and students at a small college (700 students). I am working with a 200,000 by 200,000  binary integer program that I solve, not to optimality, using Gurobi in about 24 hours. I am mostly searching for feasible schedules where students aren't double scheduled for classes but I have an objective that gives the quality of the schedule, like not violating professor requests for time preferences. 

I was wondering if constraint programming, specifically minizinc and the gecode solvers are a more efficient way to solve these kind of problems. Can constraint programing solvers solve problems with 200000 constraints and 200000 true/false variables. I need variables like  x[g,s,d,t,r] which says group g is scheduled for section s which meets at day d, time t, and room r. 

[Gleb Belov]

generally not, but it depends on the particular problem.

MiniZinc models can be efficiently linearized. You would model in a 'natural way', e.g.

array [courses] of var periods: period_of;

and CP would use those variables directly but the MIP interface would decompose into the kind of booleans you mentioned.

On Fri, Feb 2, 2018 at 1:32 PM, J. Friedman <crown...@gmail.com> wrote:

For the last year I have been working on an academic timetabling algorithm to schedule classes and students at a small college (700 students). I am working with a 200,000 by 200,000  binary integer program that I solve, not to optimality, using Gurobi in about 24 hours. I am mostly searching for feasible schedules where students aren't double scheduled for classes but I have an objective that gives the quality of the schedule, like not violating professor requests for time preferences. 

I was wondering if constraint programming, specifically minizinc and the gecode solvers are a more efficient way to solve these kind of problems. Can constraint programing solvers solve problems with 200000 constraints and 200000 true/false variables. I need variables like  x[g,s,d,t,r] which says group g is scheduled for section s which meets at day d, time t, and room r. 

--
You received this message because you are subscribed to the Google Groups "MiniZinc" group.
To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/minizinc/9e1a4edc-1935-4d09-ad7c-29ad97cb1697%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jerome H]

Hi,

Well I have started a similar project and put my files here: https://github.com/jerome-jh/fepro
Modelling still misses some details but has most of the important features. It does not use global constraints nor symetry breaking as of now.
With 3 teachers and 6 classes, it already takes "a lot of time" and I do not think I ever reached optimality once. I just launched a gecode and a chuffed instance right now for a long test run in order to have a more up to date status.

I wonder what route I should take now. I am concerned by the fact that with real data, the Minizinc model may be too slow to be useful. Still the missing constraints are the trickiest and would be best modeled with Minizinc. I may also alter my model to make use of the global constraints, with which I am not familiar.

Suggestions welcome :)

My other concern is that with real data, I have no real hope to reach optimality. So I wonder if CP is the right paradigm and if I would better turn to optimization algorithms such as local search (or MIP?).

Best regards,
Jerome.

On Friday, February 2, 2018 at 5:37:24 AM UTC+1, Gleb Belov wrote:

generally not, but it depends on the particular problem.

MiniZinc models can be efficiently linearized. You would model in a 'natural way', e.g.

array [courses] of var periods: period_of;

and CP would use those variables directly but the MIP interface would decompose into the kind of booleans you mentioned.

On Fri, Feb 2, 2018 at 1:32 PM, J. Friedman <crown...@gmail.com> wrote:

For the last year I have been working on an academic timetabling algorithm to schedule classes and students at a small college (700 students). I am working with a 200,000 by 200,000  binary integer program that I solve, not to optimality, using Gurobi in about 24 hours. I am mostly searching for feasible schedules where students aren't double scheduled for classes but I have an objective that gives the quality of the schedule, like not violating professor requests for time preferences. 

I was wondering if constraint programming, specifically minizinc and the gecode solvers are a more efficient way to solve these kind of problems. Can constraint programing solvers solve problems with 200000 constraints and 200000 true/false variables. I need variables like  x[g,s,d,t,r] which says group g is scheduled for section s which meets at day d, time t, and room r. 

--
You received this message because you are subscribed to the Google Groups "MiniZinc" group.

To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+u...@googlegroups.com.

[Jean-Noël Monette]

Hi,

One quick piece of advice on your model: Do not scale your times by
100. This makes for unnecessarily large domains. Also you do not need
to represent the exact start times of the slot, but you could just
number the start times 1 to 10 (or maybe 11 if you want to account to
for the lunch break) and the durations 1 to 4.

Otherwise, I just wanted to mention that you can keep using minizinc
with other solvers than CP ones. There exist both local search and MIP
backends to MiniZinc. You can find links on the MiniZinc website, I
think

Best,

Jean-Noël

> https://groups.google.com/d/msgid/minizinc/d29611d9-9bb0-43d8-afec-cd9e9a36fa3d%40googlegroups.com.

[Jerome H]

Hi,

Did some changes last night where I actually increased the range of the time index ;)
I wanted it to cover the full week, and that alone gave a significant speed boost (with chuffed).
The goal was to introduce the disjunctive global constraint, but that last moved actually slowed down the solver.

Still your remark is valid and I'll do the change, maybe when I code the frontend for data entry.

As for the solver, I am currently happy with chuffed: it outputs a first, very unoptimized, solution fast, then keeps improving at a slowly decreasing rate, and as a user I like that behaviour, reminding me local search. It is almost as robust as gecode, but the latter outputs an average solution fast, then nothing for hours, and as a user I dislike that.

As for the other solvers, I read than g12 was close to deprecation, cbc fails, and that's it for solvers distributed with Minizinc.

Best regards,
Jerome.

[Michael Marte]

Hi Jerome,

I agree with Jean-Noel: To speed up the model, do not use times, just use slots.

Moreover, I noticed that your problem includes teacher to course assignment, which adds a lot of complexity. In practice, however, the teacher to course assignment is usually a given and not part of the scheduling problem. So, unless actually required, I suggest to make the assignment part of the input.

Finally, I want to point you to two timetabling papers which I (co-)authored in a distant past:

• Towards constraint-based school timetabling
• University Course Timetabling Using Constraint Handling Rules

Michael

[Jerome H]

Thanks for the input. I will have to check your papers.

This project is currently on hold. My current off-work project is more signal processing related. However since my last message I turned to SAT and expressed my problem as a boolean optimization problem (MIP with only boolean variables). I read "There is no SAT problems" still decided to go this path. Took a MOOC on logic, read part of a Knuth book...

The result was that a toy problem would solve in 10min with SCIP. Minisat+ was pretty fast but would not prove optimality.

The main problem with my model is IMO that there is a huge amount of symmetries. Since there is no way yet to express teacher's preferences, many solutions give the same score. So I started to read papers on general symmetry breaking ... and struggled. This is were I left off. Maybe allowing to have teacher preferences counted in the score would have been better spent time.

Turning to SAT automatically caused time to be eliminated in favor of slots. I could also eliminate the subject variable for teachers that have only one subject as you suggest. Teachers that have several subjects could be "duplicated". Straight thoughts ... I do not have the problem completely in mind anymore.

I have a MOOC on optimization that I left partway. I will pick up a new session in september and put that project back on tracks.

Best regards,
Jerome.

[ofer strichman]

In case you are interested, I've been working on university timetabling for several years and my department has been using it since 2012. It is all based on a combination of SAT, CSP and SMT solvers. You can see details about this project here: 

https://ie.technion.ac.il/~ofers/publications/interfaces_17.pdf

Ofer