school roster

[Pieter Steenekamp]

My daughter is a teacher at a very small school (+/- 30 students and 10 teachers). Each student can take any subject that's offered and the roster has to accommodate this. 
I don't  know any optimization software, decided to learn MiniZinc to help my daughter.
I don't really have time for this, but I love my daughter and do it for her.
I know I'm asking a lot, but if there is anybody out there that can help me to solve this problem in MiniZinc I'll be very grateful. You can email me at pie...@randcontrols.co.za for the detailed specs. 
I don't really expect an answer, so I'm continuing to learn MiniZinc to do it myself.
Pieter Steenekamp
Mossel Bay, South Africa

[Jip J. Dekker]

Hi Pieter,

Welcome to the MiniZinc forums. The problem you are describing and the size of the problem should not be a problem with MiniZinc and the right solver. Although I cannot offer to create the model for you, I would suggest that (after a brief MiniZinc tutorial) you start by looking for models to similar problems. There are many rostering problems that have been solved using MiniZinc. The MiniZinc benchmarks might be a good place to start, https://github.com/MiniZinc/minizinc-benchmarks, or if you are looking for more instructional resources, then the Coursera courses  Basic Modeling for Discrete Optimization and Advanced Modeling for Discrete Optimization have lessons and assignments on scheduling and rostering.

Regards,

Jip

[Gabriel Hjort Åkerlund]

Hi Pieter,

I am willing to help you out. I will send you and email asking for the detailed specs.

Cheers,

Gabriel Hjort Åkerlund

[Gabriel Hjort Åkerlund]

Hi,

I have designed a model that I believe to capture all constraints. However, it does not perform, so I kindly request if someone could take a look at the model and see which redundant constraints are missing, or if there are any clever refinements that I've missed. Also the search strategy can doubtlessly be improved, but I haven't had time to look at it yet.

I have uploaded the model along with anonymized parameter data (for some reason, attaching the files did not work):

https://textuploader.com/18xa6

To get a smaller instance that's tractable to solve, remove entries in the StudentSubjectChoices table.

Kind regards,

Gabriel

[guido.tack]

Hi Gabriel,

The model looks good, just a few remarks:

1) I couldn't get it to produce solutions. There appears to be a bug in the alldifferent constraint, I fixed it like this:

constraint forall (s in Students)( alldifferent([ c_timeslot[sc_class[sc]] | sc in getChoicesOfStudent(s) ]) );

This could have been caught by using anonymous enums for all the index sets, but it's possible that that would have become a bit awkward to write.

With this fix, I can get a solution from Chuffed in about 25 seconds for the entire data set (no students commented out).

2) I'd remove the c_duration variables and replace the diff_n constraints with a more straightforward version:

constraint forall (c1, c2 in Classes where c1 < c2) (

  ( c_teacher[c1]=c_teacher[c2] /\ c_teacher[c1] != Null ) ->

  ( c_timeslot[c1] != c_timeslot[c2] )

);

constraint forall (c1, c2 in Classes where c1 < c2) (

  ( c_room[c1]=c_room[c2] /\ c_room[c1] != Null ) ->

  ( c_timeslot[c1] != c_timeslot[c2] )

);

This cuts down the solving time to 15 seconds.

3) The bin_packing_load is a slightly indirect way of expressing when classes are active. A more direct way, which seems to save another couple of seconds, would be

constraint forall (c in Classes) (

  c_active[c] <-> exists (sc in StudentChoices) (sc_class[sc] = c)

);

Hope this helps!

Cheers,

Guido

[Gabriel Hjort Åkerlund]

Thank you, Guido!

There was indeed a bug in the model. I tried debugging the model using findMUS, but it never hinted at alldifferent() being the culprit... Maybe I should report that as an issue, because that might be a bug in findMUS.

Hm, when I try using gecode as solver, the suggested improvements appear to decrease performance. I should point out, though, that I am using a reduced set of the student choices (not all should be included as the choices involve different periods over the year).

Nonetheless, thanks for your help!

Cheers,

Gabriel

[Pieter Steenekamp]

Hi Jip,

Thank you for your reply and advice. I've started to learn MiniZinc and to be honest I enjoy it so much that I'm actually glad you rejected my request.

Regards,
Pieter

--
You received this message because you are subscribed to a topic in the Google Groups "MiniZinc" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/minizinc/EVzLuIG-FCs/unsubscribe.
To unsubscribe from this group and all its topics, send an email to minizinc+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/minizinc/2d87eac7-b5d6-49f4-9946-d22fef1174bcn%40googlegroups.com.