Discussion Papers, Department of Finance and Management Science, Norwegian School of Economics (NHH)
No 2007/20:
Searching for optimal integer solutions to set partitioning problems using column generation
David Bredström ()
, Kurt Jörnsten ()
and Mikael Rönnqvist ()
Abstract: We describe a new approach to produce integer feasible
columns to a set partitioning problem directly in solving the linear
programming (LP) relaxation using column generation. Traditionally, column
generation is aimed to solve the LP relaxation as quick as possible without
any concern of the integer properties of the columns formed. In our
approach we aim to generate the columns forming the optimal integer
solution while simultaneously solving the LP relaxation. By this we can
remove column generation in the branch and bound search. The basis is a
subgradient technique applied to a Lagrangian dual formulation of the set
partitioning problem extended with an additional surrogate constraint. This
extra constraint is not relaxed and is used to better control the
subgradient evaluations. The column generation is then directed, via the
multipliers, to construct columns that form feasible integer solutions.
Computational experiments show that we can generate the optimal integer
columns in a large set of well known test problems as compared to both
standard and stabilized column generation and simultaneously keep the
number of columns smaller than standard column generation.
Keywords: Linear Programming; Branch and Bound tree; Lagrangian dual formulation; (follow links to similar papers)
JEL-Codes: C61; (follow links to similar papers)
15 pages, August 9, 2007
Before downloading any of the electronic versions below
you should read our statement on
copyright.
Download GhostScript
for viewing Postscript files and the
Acrobat Reader for viewing and printing pdf files.
Full text versions of the paper:
2007.pdf 
Download Statistics
Questions (including download problems) about the papers in this series should be directed to Stein Fossen ()
Report other problems with accessing this service to Sune Karlsson ()
or Helena Lundin ().
Programing by
Design by Joachim Ekebom
