next up previous
Next: The Column Generator Up: Solving Very LargeCrew Scheduling Previous: Pure Approaches

   
A Hybrid Approach

Recent research [4] has shown that, in some cases, neither the pure IP nor the pure declarative CP approaches are capable of solving certain kinds of combinatorial problems satisfactorily. But a hybrid strategy may outperform these two methods. When contemplating a hybrid strategy, it is necessary to to decide which part of the problem will be handled by a constraint solver, and which part will be dealt with in a classical way. Given the huge number of columns at hand, the use of a column generation approach seemed to be almost mandatory.

A declarative constraint language is particularly suited to express the feasibility constraints imposed by the original problem in a clear and concise way. Furthermore, a constraint model of the original problem can also be easily turned into an efficient column generator by adding one extra constraint to the model: the generated duties must have a negative reduced cost so as to improve the objective function value [1]. Moreover, when looking for new feasible duties (columns) to enter the basis in the current set partitioning formulation, it is not necessary to find the one with the most negative reduced cost. This removes the minimization constraint from the formulation, rendering it much more efficient. Our hybrid strategy implemented a column generation approach where new columns were generated on demand by a declarative constraint program.

We decided to use the ABACUS 3 branch-and-price framework in order to save programming time. The Linear Programming relaxations of the set partitioning formulation of the problem are solved inside ABACUS with the help of a CPLEX4 3.0 LP solver. When the ABACUS process has solved the current master problem to optimality, it sends the values of the dual variables to the constraint solver, together with the number of columns with negative reduced costs it would like to get. If there remained some such columns, a subset of them is captured by the CP solver and sent back to the ABACUS process, and the cycle starts over. If there are no such columns, the LP solver has found an optimal solution. Having found the optimal solution for the current node of the enumeration tree, its dual bound has also been determined. The normal branch-and-bound algorithm can then proceed until it is time to solve another LP at a different node of the implicit enumeration tree. By experimenting with the data sets at hand, we determined that the number of columns with negative reduced cost to request at each call of the CP solver was best set to 53.



 
next up previous
Next: The Column Generator Up: Solving Very LargeCrew Scheduling Previous: Pure Approaches

1999-12-16