Column-based model formulations

Sometimes, we face management problems with quite complicated constraints, which seem to defy the best modeling efforts. Column-based model formulations are a formidable tool, which is again best illustrated by a simple example, namely, a stylized staffing problem.

Imagine that we are running a post office, or something like that, with a lot of counters; alternatively, if you prefer, imagine a retail store with cashier’s desks. During the day, we need not keep a fixed number of desks open; there are peak hours at which we need more people, and other time periods at which many desks may be left closed without running the risk of customers experiencing large waiting times at queues. Suppose that each day consists of eight opening hours, t = 1, 2, …, 8, and that we have time-varying requirements represented by R_t, t = 1, …, 8, i.e., the minimum number of desks/counters that should be open during time bucket t. We would like to find the minimal number of people to hire, taking into account the constraints on the way shifts must be organized. For instance, let us assume that each shift consists of four consecutive hours, with one hour of rest that may be either the second or the third one. To state it more clearly, the work pattern may be one of the following:

1. Work, rest, work, work
2. Work, work, rest, work

The pattern may start at t = 1, 2, 3, 4, 5; of course, no pattern can start during the last hours of each day. How many workers should we hire for each possible pattern, in order to find a staffing schedule with minimal cost?

This is a drastically simplified case, but expressing regulatory requirements on work patterns is a real-life issue in crew scheduling problems, for both airlines and train transportation companies. However, there is a standard way to represent the problem in terms of combining columns of a matrix. Recall that solving a system of linear equations Ax = b is essentially the problem of expressing vector b as a linear combination of the columns of matrix A.²⁶ Here we may define a set of columns representing the possible work patterns; each column is a vector of 8 elements, which may be 1 or 0, where a 1 in position t means that the worker is active during hour t. The possible patterns are

There are 10 columns a_j j = 1, …, 10, that can be grouped into a matrix , where element a_tj is set to 1 if the worker following pattern j is active at hour t, 0 otherwise. Let us denote by x_j the number of workers hired and following pattern j. The total number of workers active at hour t can be written as

and this should not be less than the requirement R_t. We may minimize the total cost of staffing by solving the ILP:

In this stylized case, we had just 10 columns. In more practical settings, we may have to do with a huge number of columns. Then, it may be a wiser strategy to generate only useful columns, which provide us with interesting building blocks that we may assemble to solve the overall problem. Such columns can be generated dynamically as needed. Quite sophisticated (and effective) column generation strategies have been devised to solve seemingly intractable problems. As they are typically quite problem-dependent, they are beyond the scope but it is important to understand that quite involved constraints may be taken into account in the process of generating columns; this level of complexity is separated from the issue of putting building blocks together, resulting in a nice decomposition of the overall problem.