Optimizing working scheduling MiniZinc code - constraint programming

Question

Please can you help optimize this working MiniZinc code:

Task: There is a conference which has 6x time slots. There are 3 speakers attending the conference who are each available at certain slots. Each speaker will present for a predetermined number of slots.

Objective: Produce the schedule that has the earliest finish of speakers.

Example: Speakers A, B & C. Talk durations = [1, 2, 1]

Speaker availability:

+---+------+------+------+
|   | Sp.A | Sp.B | Sp.C |
+---+------+------+------+
| 1 |      | Busy |      |
| 2 | Busy | Busy | Busy |
| 3 | Busy | Busy |      |
| 4 |      |      |      |
| 5 |      |      | Busy |
| 6 | Busy | Busy |      |
+---+------+------+------+

Link to working MiniZinc code: http://pastebin.com/raw.php?i=jUTaEDv0

What I'm hoping to optimize:

% ensure allocated slots don't overlap and the allocated slot is free for the speaker
constraint 
    forall(i in 1..num_speakers) (
        ending_slot[i] = starting_slot[i] + app_durations[i] - 1
    ) /\
    forall(i,j in 1..num_speakers where i < j) (
        no_overlap(starting_slot[i], app_durations[i], starting_slot[j], app_durations[j])
    ) /\
    forall(i in 1..num_speakers) (
        forall(j in 1..app_durations[i]) (
            starting_slot[i]+j-1 in speaker_availability[i]
        )
    ) 
;

Expected solution:

+---+----------+----------+----------+
|   |   Sp.A   |   Sp.B   |   Sp.C   |
+---+----------+----------+----------+
| 1 | SELECTED | Busy     |          |
| 2 | Busy     | Busy     | Busy     |
| 3 | Busy     | Busy     | SELECTED |
| 4 |          | SELECTED |          |
| 5 |          | SELECTED | Busy     |
| 6 | Busy     | Busy     |          |
+---+----------+----------+----------+

Disconnect

Did you try different solvers? You'll find a list if available solvers here hakank.org/minizinc Also the minizinc challenge results are available here minizinc.org/challenge2013/challenge.html You'll have an idea regarding best solvers.. – Gleet

Answer 1

I'm hakank (author of the original model). If I understand it correctly, your question now is how to present the table for the optimal solution, not really about finding the solution itself (all FlatZinc solvers I tested solved it in no time).

One way of creating the table is to have a help matrix ("m") which contain information if a speaker is selected (1), busy (-1) or not available (0):

array[1..num_slots, 1..num_speakers] of var -1..1: m;

Then one must connect info in this the matrix and the other decision variables ("starting_slot" and "ending_slot"):

% connect to matrix m
constraint
   forall(t in 1..num_slots) (
      forall(s in 1..num_speakers) (
         (not(t in speaker_availability[s]) <-> m[t,s] = -1) 
          /\
          ((t >= starting_slot[s] /\ t <= ending_slot[s]) <-> m[t,s] = 1)
     )
 )

;

Then the matrix "m" can be printed like this:

% ...
++
[ 
   if s = 1 then "\n" else " " endif ++
   if fix(m[t,s]) = -1 then 
      "Busy    " 
   elseif fix(m[t,s]) =  1 then 
      "SELECTED" 
   else
      "        "
   endif
 | t in 1..num_slots, s in 1..num_speakers

] ;

As always, there are more than one way of doing this, but I settled with this since it's quite direct.

Here's the complete model: http://www.hakank.org/minizinc/scheduling_speakers_optimize.mzn

Update: Adding the output of the model:

Starting:  [1, 4, 3]
Durations: [1, 2, 1]
Ends:      [1, 5, 3]
z:         5

SELECTED Busy             
Busy     Busy     Busy    
Busy     Busy     SELECTED
         SELECTED         
         SELECTED Busy    
Busy     Busy             
----------
==========

Update 2: Another way is to use cumulative/4 instead of no_overlap/4 which should be more effective, i.e.

constraint 
    forall(i in 1..num_speakers) (
    ending_slot[i] = starting_slot[i] + app_durations[i] - 1
    ) 
    % /\ % use cumulative instead (see below)
    % forall(i,j in 1..num_speakers where i < j) (
    %   no_overlap(starting_slot[i], app_durations[i], starting_slot[j], app_durations[j])
    % ) 
    /\
    forall(i in 1..num_speakers) (
    forall(j in 1..app_durations[i]) (
        starting_slot[i]+j-1 in speaker_availability[i]
           )
    ) 

    /\ cumulative(starting_slot, app_durations, [1 | i in 1..num_speakers], 1)
;

Here's the altered version (which give the same result) http://www.hakank.org/minizinc/scheduling_speakers_optimize2.mzn (I've also skipped the presentation matrix "m" and do all presentation in the output section.)

For this simple problem instance, there is no discernible difference, but for larger instances this should be faster. (And for larger instances, one might want to test different search heuristics instead of "solve minimize z".)

Episode

Since it's not so easy to do experiments in MiniZinc, here's an Picat model using the same approach: hakank.org/picat/scheduling_speakers_optimize.pi It solves a problem with 20 speakers (where some speaker has 2 slots to speak) and 24 slots in ~0s. – Episode

I added a 50 speakers x 60 slot problem to the second MiniZinc model (scheduling_speakers_optimize2.mzn). It was solved by Gecode, Google or-tools, Choco3 in 0.1s; most other solvers took < 1s. – Episode

For some reason the MiniZinc model with 50 speakers & 60 slots is taking a very long time to solve on my PC. 5 minutes now and still waiting! Do you have a link to the Google ORtools version please as I'm trying to convert the MiniZinc model to a C# Google OR-tools version? – Disconnect

The G12 MiniZinc solvers ("fd","lazy", and "cpx") takes very long to solve the 50x60 problem, perhaps because their "cumulative" is not strong enough. Google OR-tools can be downloaded from code.google.com/p/or-tools . Gecode can be downloaded here: gecode.org . – Episode

For a subset of these scheduling problems - when there must be exactly one speaker in all slots - I did a MiniZinc model that is much faster for the MiniZinc solvers: hakank.org/minizinc/scheduling_speakers_optimize3.mzn . MiniZinc "fd" solver solves the 50x60 instance in 4 seconds (where most of the time is FlatZinc flattening). Please note that this model will not solve the original problem since it have holes in the schedule. (That might be fixed by adding dummy speakers.) – Episode

I have now changed hakank.org/minizinc/scheduling_speakers_optimize3.mzn so it now detects if there is holes in the schedule (i.e. when sum(app_durations) < num_slots) and then change the constraint accordingly. MiniZinc "fd" solver now solves this in < 1s (plus some seconds of Flattening). The time of flattening can be halved by using the "--no-optimise" flag. – Episode

hakank.org/minizinc/scheduling_speakers_optimize3.mzn now includes two larger problems: 100x140 solved by MiniZinc/fd in 8.8s (including flattening) and 200x220 which it's probably too large memory wise for MiniZinc fd. Gecode solves the larger problem in 2.7s (+ 16s flattening). – Episode

Thanks, your website has been very helpful for teaching me CP. I'm trying to write this in C# for OR-tools but I'm stuck. Do you have a working version in C# for OR-tools available please? – Disconnect

Sorry, but I haven't modeled this problem in or-tools/C# (or any other systems except MiniZinc and Picat). – Episode

Thanks. I'm having real difficulty adapting hakank.org/google_or_tools/scheduling_speakers.cs to account for a duration. Any pointers on how to write this in C#? – Disconnect

Perhaps I'll look the C# model later on, though probably not today. One thing is to convert the very important "cumulative" to MakeFixedDurationIntervalVar (or similar). See for example my simple Furniture Moving example using intervals: hakank.org/or-tools/furniture_moving_intervals.cs . Also, reifications is handled different in or-tools since there is AFAIK no syntactic for these, so one have to use "MIP tricks". Some examples are hakank.org/or-tools/alldifferent_except_0.cs and hakank.org/or-tools/who_killed_agatha.cs . There is a IsMember() which is handy. – Episode

Thanks - right now I have a working solution but it's based using your MyCumulative function as I've only managed to get it working with IntVar. – Disconnect

How large are your problem instances? Do they has holes in the schedule? Perhaps you should first try to port your original version, i.e. with no_overlap etc and see how well it do in or-tools/C#. – Episode

This is the best I've come up with in C#: pastebin.com/Cp1xPkEe It outputs a solution almost instantly but takes a long time (minutes) to complete. Can you help me improve this please? – Disconnect

I might look at it later today. The problem instance from your C# code is now added to hakank.org/minizinc/scheduling_speakers_optimize3.mzn . or-tools' FlatZinc solver solves it in no time (0.4s including flattening). – Episode

Here's a model in or-tools/C#: hakank.org/or-tools/scheduling_speakers_optimize.cs . It solve your 18 speaker problem in 0.07s, and the generated 100x140 problem (included in the model) is solved in 0.5s. The extra matrix ("m") is not needed since the "interval constraint" is fast enough. Also, I had to fix some offsets since it don't work exactly like "cumulative" in MiniZinc. It seems to work, but please check it before any serious use. – Episode

Thanks, I understand how this code is working. However it won't solve this data when you set the minimum starting slot to be 7 (line 241), although there are solutions: pastebin.com/raw.php?i=i93TTv9E Any idea how to make this work? – Disconnect

What do you mean that it won't "solve the data"? When setting "starts[s] = 7;" it give a (tenative) solution of 34. This for both your original problem instance and the pastebin you linked to. Perhaps you mean that it don't find an optimal solution in no time (which - in my book - is another thing from "don't solve the data")? – Episode

Well, you can try to change the labeling in makePhase to Solver.CHOOSE_RANDOM and Solver.ASSIGN_MAX_VALUE. It's not as fast on the 100x140 problem but solves both (or was it the same) your problem(s) in some seconds. – Episode

When the min start slot is 7 then using the first 1..6 slots is a complete waste of resources. So one way is to ignore these slots altogether and make slot 7 to be slot 1, i.e. to adjust all the availability times etc. – Episode

Another thing: Since we know that z <= 34 (which is shown directly by the model), then you can set ends[s] = 35 instead of = numSlots-duration[s]. This give an optimal solution much faster. – Episode

Hi Hakank, by "won't solve the data", I was waiting minutes and it hadn't outputted a solution. To give a bit more information, I want to present the end user a choice of possible start slots and durations for the schedule. So I plan on running this many times in a loop from starting slot 1 to (total slots - speakers). It's important it runs as fast as possible so the user isn't waiting - it'll be on a web application. – Disconnect

Answer 2

As I commented on your previous question Constraint Programming: Scheduling speakers in shortest time, the cumulative constraint is appropriate for this. I don't have Minizinc code handy, but there is the model in ECLiPSe (http://eclipseclp.org):

:- lib(ic).
:- lib(ic_edge_finder).
:- lib(branch_and_bound).

solve(JobStarts, Cost) :-
    AllUnavStarts = [[2,6],[1,6],[2,5]],
    AllUnavDurs   = [[2,1],[3,1],[1,1]],
    AllUnavRess   = [[1,1],[1,1],[1,1]],
    JobDurs = [1,2,1],
    Ressources = [1,1,1],
    length(JobStarts, 3),
    JobStarts :: 1..9,

    % the jobs must not overlap with each other
    cumulative(JobStarts, JobDurs, Ressources, 1),

    % for each speaker, no overlap of job and unavailable periods
    (
        foreach(JobStart,JobStarts),
        foreach(JobDur,JobDurs),
        foreach(UnavStarts,AllUnavStarts),
        foreach(UnavDurs,AllUnavDurs),
        foreach(UnavRess,AllUnavRess)
    do
        cumulative([JobStart|UnavStarts], [JobDur|UnavDurs], [1|UnavRess], 1)
    ),

    % Cost is the maximum end date
    ( foreach(S,JobStarts), foreach(D,JobDurs), foreach(S+D,JobEnds) do true ),
    Cost #= max(JobEnds),

    minimize(search(JobStarts,0,smallest,indomain,complete,[]), Cost).

Tanka