A Hybrid Approach

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 CPLEX^{4} 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.