Seminar scheduling with OML

In response to my series on office space allocation models, I received an email from a reader who is trying to adapt the code to solve a related problem. Here is a reworded description of his problem:

  1. I need to assign people to tables for each week of a three-week seminar.
  2. I have 8 people.
  3. I have 4 tables / PCs.
  4. For the second week of the seminar, I don’t want the groups to be the same, and each person must not be at the same table.
  5. For the third and last week these conditions are the same, taking into account the previous two weeks.

The reader was almost able to figure it out but got stuck on the “different groups” and “different tables” constraints. Let’s work through the problem and build an OML model. I like to start by defining the sets for my problem. In this case, they are:

  • People. To be consistent with my previous posts I will call them “Entities”. There are 8 of them.
  • Tables. There are 4 of them.
  • Time periods. There are 3 of them (one week duration).

What do I want Solver Foundation to compute? The assignment of entities to tables for each period. So let’s add a 0-1 integer decision called “assign[e, t, p]” that is 1 if and only if Entity e is assigned to Table t for Period p. If I have this decision then it is easy to write two constraints which are not explicitly stated in the problem description, but which must hold:

  • Assign all: Each entity is assigned to exactly one table for each time period.
  • Two per table: there are two entities per table.

Now I’ve got to handle the “different tables” and “different groups” constraints. It seems natural to use the Unequal operator – this operator forces all of the arguments inside to be different. For “same table” what I want to say is “for each entity, the entity is assigned to a different table over all time periods.” But the “assign” decision is not very helpful; instead I want a decision “table[e, p]” which evaluates to the table that entity e is assigned to for period p. But using a modeling trick I can actually get values for this “table” decision by summing over assign[e, t, p] for a fixed entity and time period and multiplying each by “t”.

The last constraint is the “same group” constraint. This is a bit tricker. Suppose Adam and Bonnie are assigned to table 4 during week 1. I need to make sure that Adam and Bonnie are not assigned to the same table (it doesn’t matter which one) for all other weeks. To model this, I can compute what amounts to a hash (called “group”) for each entity and period. Let’s define group[e, p] to be the sum of all the entity IDs at the same table as Entity e for Period p. If I have this hash then I can simply say that group[e, p] must be different for each period p.

The OML model is below. If you want to try it out, open Excel, flip to the Solver Foundation tab, click on the “Model” tab, change to “Manual” mode, paste the OML, and click Solve.

Two more notes:

  • I need to specify that there are 8 people, 4 tables, and 3 time periods. I do this by specifying ranges in the “assignAll” constraint. This implicitly establishes the values for the Entities, Tables, and Periods sets.
  • The Unequal operator can only be used in Constraint Programming models. CP models cannot contain any real-valued parameters or decisions. It is also possible (I think) to write a mixed integer programming model for this problem but it’s messier.
Model[
  Parameters[Sets[Integers], Entities, Tables, Periods],
  Decisions[Integers[0, 1],
    assign[Entities, Tables, Periods]
  ],
  Decisions[Integers[0, Infinity], 
    table[Entities, Periods], group[Entities, Periods]
  ],

  Constraints[
    assignAll -> Foreach[{e, 0, 8}, {p, 0, 3}, 
        Sum[{t, 0, 4}, assign[e, t, p]] == 1
    ],

    twoPerTable -> Foreach[{p, Periods}, 
      Foreach[{t, Tables},
        Sum[{e, Entities}, assign[e, t, p]] == 2
      ]
    ],

    whichTable -> Foreach[{e, Entities}, {p, Periods}, 
      table[e, p] == Sum[{t, Tables}, t * assign[e, t, p]]
    ],

    differentTables -> Foreach[{e, Entities},
      Unequal[Foreach[{p, Periods}, table[e, p]]]
    ],

    whichGroup -> 
      Foreach[{e1, Entities}, {p, Periods},
        group[e1, p] == Sum[{t, Tables}, 
          assign[e1, t, p] * Sum[{e2, Entities}, e2 * assign[e2, t, p]]]
      ],

    differentGroups -> Foreach[{e, Entities}, 
      Unequal[Foreach[{p, Periods}, group[e, p]]]
    ]
  ]
]

Author: natebrix

Follow me on twitter at @natebrix.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s