Columnwise Formulations in AMPL

Consider the following problem (Adapted from Section 16.2, AMPL: A Modeling Language for Mathematical Programming):

=!WorkHard= and Co are scheduling workers for their production shifts during the week. All workers are paid the same wage, so they want to minimise the number of workers needed.

Their are three shifts during the week (Mon-Fri) and two on Sat. The daily shifts require 100, 78 and 52 employees respectively.

Union rules require that employees work 5 shifts a week, but only 1 shift in 24 hrs.

How many workers do !WorkHard need to staff their production plant?

We can define the set of shifts and the number of workers required for each shift:

set SHIFTS;  # The shifts
# The number of workers needed per shift
param Required {SHIFTS};

We can also define the number of work schedules and the list of shifts each schedule covers:

param Nsched; # The number of work schedules
# The set of work schedules
set SCHEDS := 1..Nsched;
# The shifts covered by each schedule
set SHIFT_LIST {SCHEDS} within SHIFTS;

We can define a set covering problem in the usual way:

\begin{verbatim}
var Work {SCHEDS} >= 0, integer;

minimize TotalWorkers :
sum {j in SCHEDS} Work[j];

subject to ShiftNeeds {i in SHIFTS} :
sum {j in SCHEDS : i in SHIFT_LIST[j]}
Work[j] >= Required[i];
\end{verbatim}

Note that each constraint requires us to search all our variables to find the coefficients. If our data is defined in terms of the variables, we can express our mathematical programme using a columnwise formulation.

First, we define the objective function and constraints, but we don't specify any coefficients (note that {\tt to_come} tells AMPL that the (non-zero) left-hand side coefficients for the constraints will be defined at the same time as the associated variable) :

\begin{verbatim}
minimize TotalWorkers;
subject to ShiftNeeds {i in SHIFTS} :
to_come >= Required[i];
\end{verbatim}

Then, we define our variables along with their objective and constraint coefficients, using the reserved words {\tt obj} (for the associated non-zero objective coefficient) and {\tt coeff} (for the associated non-zero left-hand side coefficients - one for each such constraint):

\begin{verbatim}
var Work {j in SCHEDS} >= 0, integer,
obj TotalWorkers 1,
coeff {i in SHIFT_LIST[j]} ShiftNeeds[i] 1;
\end{verbatim}

Thus, each {\tt Work} variables has a coefficient of 1 in the {\tt TotalWorkers} objective function and a coefficient of 1 in all the {\tt ShiftNeeds} constraints for shifts in the schedule. In this way we can build up the objective function and the constraint left-hand sides with each variable definition. Furthermore, if a variable has a coefficient equal to 0 in the objective function (or the left-hand side of a constraint) we do not define that coefficient (thus reducing the necessary memory required to store the model).

This is an elegant solution if the constraint coefficients are defined in terms of the variables rather than the constraints. One problem remains, how do we define our work schedules? We can use either a depth-first search or power sets.

-- MichaelOSullivan - 06 May 2008