The Meeting Scheduling Problem (prob046)
---------------------------------------

The meeting scheduling problem is described in cspLib http://csplib.org/ as prob046. 


Introduction
------------
The 27 instances in cspLib have been reformatted and are in the problem directory with one file for each problem.
The format of the files can be explained using the problem below. We have 10 meetings (n=10), 5 agents (m=5) and
18 time slots to schedule the meetings. We then have an m by n array "attends" where attends[i][j] = 1 iff agent_i
attends meeting_j. There is then an n by n distance array where distance[i][j] is the time to travel from meeting_i
to meeting_j. All meetings take one unit of time and the first time slot is 0 (zero). 

10 5 18

0: 0 0 0 0 0 0 0 1 0 1
1: 0 1 1 0 1 1 1 1 0 1
2: 0 0 0 0 0 1 0 1 1 0
3: 0 1 0 0 1 0 0 1 0 0
4: 1 0 1 0 0 0 1 1 1 0

0: 0 1 2 1 1 2 1 2 2 2
1: 1 0 2 2 1 1 1 1 1 2
2: 2 2 0 2 1 2 1 1 1 2
3: 1 2 2 0 1 2 1 2 2 1
4: 1 1 1 1 0 2 1 2 1 2
5: 2 1 2 2 2 0 2 1 2 2
6: 1 1 1 1 1 2 0 1 2 1
7: 2 1 1 2 2 1 1 0 2 2
8: 2 1 1 2 1 2 2 2 0 2
9: 2 2 2 1 2 2 1 2 2 0


The problem is then to schedule the meetings in the given amount of time (0 to timeSlots-1). Below is a solution
to the above problem (rProblems/10-5-30-2-00.txt) where meeting_0 starts at time 12, meeting_1 starts
at time 15, ..., meeting_9 starts at time 12. This took 24 milliseconds to solve and 11 nodes.

>> java Go rProblems/10-5-30-2-00.txt -solve
0 12
1 15
2 0
3 0
4 9
5 6
6 2
7 4
8 9
9 12
24[+0] millis.
11[+0] nodes

We can validate that this is a solution using the program Validate that produces a small gantt chart and
checks if the schedule is valid. NOTE: it does NOT check that the schedule is within the time window given.

>> java Validate rProblems/10-5-30-2-00.txt rProblems/solve-10-5-30-2-00.txt 
 0: ------------X (12)
 1: ---------------X (15)
 2: X (0)
 3: X (0)
 4: ---------X (9)
 5: ------X (6)
 6: --X (2)
 7: ----X (4)
 8: ---------X (9)
 9: ------------X (12)
true

Also note that the above schedule is NOT optimal! Below is an optimal schedule that uses only 13 time slots,
and program Optimize took 202 millisecond to run and explored 227 nodes.

>> java Go rProblems/10-5-30-2-00.txt -opt
0 12
1 6
2 0
3 0
4 8
5 4
6 10
7 2
8 7
9 12
202[+0] millis.
227[+0] nodes


toDo (minizinc)
---------------
 1. Code up msp.mzn and test it (initially) on eu.dzn. Your model should produce a feasible schedule.
    NOTE: there are insolvable cspLib instances.

   > minizinc msp.mzn eu.dzn

 2. Validate your results (see above).

 3. Modify msp.mzn such that it produces an optimal schedule, i.e. schedule all meetings
    in the least amount of time.

 4. To do more testing, you can convert problem instances to dzn format as follows

    > java toDzn rProblems/10-5-30-2-00.txt > 10-5-30-2-00.dzn
    > minizinc msp.mzn 10-5-30-2-00.dzn



toDo (choco)
------------
 1. Code up MSP.java and test it on the cspLib instances in problems/* and the new instances
    in rProblems/*. Use the Validate program to validate your results.
    NOTE: there are insolvable cspLib instances.

 2. Some of the problems are hard! So, use a time out limit on the command line as follows:

    >> java Go rProblems/40-10-20-9-00.txt -opt -time 10000

    will terminate after 10 seconds cpu time and report the best result found so far, and 

    >> java Go rProblems/40-10-20-9-00.txt -opt

    will terminate (eventually, but maybe not in your lifetime) with the optimum solution.


 3. Investigate alternative variable ordering heuristics for the problem


Patrick Prosser
December 2018