Example: Conference

Problem Specification

We want to construct the time table of a conference. The conference will consist of 11 sessions of equal length. The time table is to be organized as a sequence of slots, where a slot can take up to 3 parallel sessions. There are the following constraints on the timing of the sessions:

• Session 4 must take place before Session 11.
• Session 5 must take place before Session 10.
• Session 6 must take place before Session 11.
• Session 1 must not be in parallel with Sessions 2, 3, 5, 7, 8, and 10.
• Session 2 must not be in parallel with Sessions 3, 4, 7, 8, 9, and 11.
• Session 3 must not be in parallel with Sessions 5, 6, and 8.
• Session 4 must not be in parallel with Sessions 6, 8, and 10.
• Session 6 must not be in parallel with Sessions 7 and 10.
• Session 7 must not be in parallel with Sessions 8 and 9.
• Session 8 must not be in parallel with Session 10.

The time table should minimize the number of slots.

Viewpoint

The model has a variable nbSlots saying how many slots the conference has. Here, nbSlots can be constrained to the finite domain $\ensuremath{\{4,\dots,11\}}$. The model also has a variable plan_i for every session i, where plan_i stands for the number of the slot in which Session i will take place. Every variable plan_i can be constrained to the finite domain 1# nbSlots. The remaining constraints are obvious from the problem description.

Branching Strategy

We use a two-dimensional branching strategy. We first branch on nbSlots, trying smaller values first. Once nbSlots is determined, we branch on the variables plan_i using the standard first-fail strategy.

Script

The script in Listing 13 first creates a local variable nbSlots specifying the number of slots used by the conference. It also defines two procedures precedes and notparallel that realize scheduling constraints and should be easy to understand. It then branches naively on nbSlots. After nbSlots is determined, it constrains its variable plan.

The statement

Explorer.exploreOne(conference)

will explore the search tree until the first solution is found. The first solution minimizes the number of slots and looks as follows:

{x1 = intvar{|1 |},
x10 = intvar{|3 |},
x11 = intvar{|4 |},
x2 = intvar{|2 |},
x3 = intvar{|3 |},
x4 = intvar{|1 |},
x5 = intvar{|2 |},
x6 = intvar{|2 |},
x7 = intvar{|3 |},
x8 = intvar{|4 |},
x9 = intvar{|1 |}}

This plan says that the conference requires 4 slots, where the sessions 1, 4 and 9 take place in slot 1, the sessions 2, 5 and 6 take place in slot 2, the sessions 3, 7 and 10 take place in slot 3, and the sessions 8 and 11 take place in slot 4.

fun conference space =
    let 
        val nbSlots = FD.range(space,(4,11)) 
        val plan as 
           #[x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11] =
           FD.rangeVec(space,11,(1,11))
        fun precedes(a,b)= post(space,FD(a)`< FD(b),FD.DOM)
        fun notparallel(s,vec)= Vector.app(fn x => 
            post(space,FD(s)`<> FD(x),FD.DOM))vec
        
    in
        FD.branch(space,#[nbSlots],FD.B_NONE,FD.B_MIN);
        Vector.app(fn x => FD.rel(space,x,FD.LQ,nbSlots))plan;
        precedes(x4,x11);
        precedes(x5,x10);
        precedes(x6,x11);
        notparallel(x1,#[x2,x3,x5,x7,x8,x10]);
        notparallel(x2,#[x3,x4,x7,x8,x9,x11]);
        notparallel(x3,#[x5,x6,x8]);
        notparallel(x4,#[x6,x8,x10]);
        notparallel(x6,#[x7,x10]);
        notparallel(x7,#[x8,x9]);
        notparallel(x8,#[x10]);
        (* the next line ensures that every slot has at most 
           three sessions *)
        Vector.app(fn x =>FD.countVI(space,plan,x,FD.LE,4))plan;
        FD.branch(space,plan,FD.B_SIZE_MIN,FD.B_MIN);
        {x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11}
    end