Mathematical Formulation

The following describes a subset of the full formulation.

There are three decision variables associated with every activity: resource assignment, start time, and duration. The resource assignment is an integer mapping from the activity to a specific room (resource). This mapping is one to many, where an activity is assigned to only one room, but a resource may hold many activities. A succinct integer formulation was chosen rather than using one binary variable per event/room combination. If a MILP formulation had been used, binary variables might have been preferable. The start time and duration define an uninterrupted interval of time in which the event takes place. Both variables are integers in this formulation, although in alternative formulations such as MILP, it might be more efficient and flexible to treat them as continuous variables.

A formal definition follows:

A set T of tasks (activities) are assigned to a set Res of resources (rooms). Every activity i T has three associated decision variables: assignmenti Res , starti I , and durationi I . So every activity is assigned to one and only one room. The parameters startconf I and durationconf I define the time interval of the entire conference. So for all starti I and durationi I , startistartconf and starti + durationistartconf + durationconf. In other words, an activity is defined by a contiguous time interval bounded by the time interval of the overall conference.

Additionally, resource consumption is defined by usagert R , for every r Res and every t I where startconft startconf + durationconf. An upper bound of one is defined on all values of usagert. Assignment of a task to a resource consumes one unit of the resource defined by the assignment and time interval. So for every i T , one unit of usagert is consumed where r = assignmenti and for every t , such that startit starti+ durationi. The effect of these constraints is that two tasks cannot overlap in the same time interval if they are assigned to the same resource.

A schedule is a feasible choice for all decision variables. In addition to the constraints described above, hard constraints can be defined excluding arbitrary values of assignmenti, starti, and durationi for all i T . Also, hard constraints can be defined between pairs of tasks. Specifically, non-overlap constraints can be defined between pairs of tasks, independent of the room assignments. Given a non-overlap constraint on the tasks i T and j T , the disjunction of the following two expressions must be true: starti + durationistartj or startistartj+ durationj.

When creating a feasible solution, the following objective is maximized:

plAssignmenti, plStarti, and plDurationi are parameters of the problem that define piecewise linear functions of decision variables. In particular, plAssignmenti is based on the combination of preferences for properties of rooms. For the purposes of optimization, these individual preferences can be precomputed into a single function, plAssignmenti, so the details are omitted.

Back to Optimizer page | Back to Modules summary page | Back to Core index page | Back to Main project page