Pure Approaches

When adopting IP approaches to solve this problem,
one usually ends up with a set partitioning formulation where the
elements of *F* constitute the columns of the coefficient matrix.
The pure IP formulation of the problem is:

where

Due to the size of *F*, an implicit way to treat the set of feasible
duties is needed.
Column generation [1] is a technique that is
widely used to handle linear programs which
have a very large number of columns in the coefficient matrix.
The method works by repeatedly executing two phases.
In a first phase, instead of solving a linear relaxation of the whole problem,
in which all columns are required to be loaded in memory, we quickly solve a
smaller problem. This problem is called the *master* problem,
and deals only with a subset of the original columns.
That smaller problem solved, we start phase two, looking for columns
with a negative reduced cost.
If there are no such columns, we have proved that the solution at hand indeed
minimizes the objective function.
Otherwise, we augment the master problem by bringing in a number of columns
with negative reduced costs, and start over on phase one.
From the IP formulation above, the reduced cost of a feasible duty
*d* is given by
,
where *T* is the
set of trips serviced by *d* and *u*_{j} is the value of the dual variable
associated with trip *j*.
The problem of computing columns with negative reduced
costs is called the *slave* subproblem.
When the original variables are restricted to integer values, this algorithm must be
embedded in a branch-and-bound strategy.
The resulting algorithm is usually referred to as *branch-and-price*.
The slave subproblem can be modeled as a constrained shortest path
problem over a directed acyclic graph and it can be solved by a dynamic
programming algorithm [3]. Nevertheless, the
pseudo-polynomial algorithms that arise from this strategy turn out
to be very time consuming. This is mainly because of the looseness of
our problem constraints [8].

Difficulties also arise when trying to solve crew scheduling problems using pure constraint satisfaction techniques [2,6,8]. The huge search space can only be dealt with efficiently when pruning is enforced by strong local constraints. Besides, a simple search strategy, lacking good problem specific heuristics, is very unlikely to succeed. When solving scheduling problems of this naturem to optimality, none of the these requirements can be easily met, rendering it intrinsically difficult for pure CP techniques to produce satisfactory results in these cases.