School Seminars and Colloquia

Decomposition and column generation in integer programming

OR Seminar

by Jørgen Tind


Institution: Institute for Mathematical Sciences, University of Copenhagen.
Date: Wed 21st December 2005
Time: 2:15 PM
Location: Classroom 213, Richard Berry Bldg, University of Melbourne

Abstract: The idea of decomposition is a fundamental discipline in mathematical programming with important contributions in theory and
applications. The classical Dantzig-Wolfe and Benders decomposition
procedures based on linear programming duality have had a great impact on research in mathematics, engineering and economics.
The classical ideas can be extended to more general optimization problems by using an appropriate duality theory.
The purpose of this talk is to present a decomposition and column generation procedure in integer programming using integer programming duality. Application of the classical decomposition and column generation
procedure based on linear programming solves the linear programming relaxation of the actual integer programming problem. We shall here demonstrate a procedure leading to an optimal integer solution.
Applications in multicriteria optimization shall be pointed out.
(The presentation is based on joint work with Matthias Ehrgott, The University of Auckland).

For More Information: Mark Fackrell tel. 8344 8053 email: m.fackrell@ms.unimelb.edu.au