School Seminars and Colloquia

Cardinality constraints and column generation

ORSUM Seminar

by Robert Johnston


Institution: Honorary Professorial Fellow, University of Melbourne
Date: Fri 6th May 2005
Time: 1:05 PM
Location: Room 213, Richard Berry Building, University of Melbourne

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