Cardinality constraints and column generation
by Robert Johnston
Abstract: In many combinatorial optimisation problems where there are a huge number of
potential activity vectors (often called patterns), mathematical programming
approaches can only be attempted by column generation. In this technique,
explicit consideration of each activity vector is avoided by only generating
the vectors when required. The sub-problem to be solved for vector generation
varies from problem to problem and some examples will be briefly introduced.
A major problem with the column generation approach however is that it does
not permit apparently simple extra constraints. Two important ones are
- a cardinality limit on the number of patterns in the solution
- lower bounding on activity levels.
The object of our ARC funded project is to determine how the column generation
technique might in general be modified to overcome these difficulties.
This talk discusses how for the cutting stock problem - an
archetypal column generation application - the column generation sub-problem,
in this case the solving of knapsack problems, can be extended to help
produce a relatively compact Mixed Integer Program that solves the problem
with these two extra constraints.
For More Information: Mark Fackrell tel: 8344-8053 e-mail: M.Fackrell@ms.unimelb.edu.au