Discussion Papers, Department of Business and Management Science, Norwegian School of Economics (NHH)
Searching for optimal integer solutions to set partitioning problems using column generation
(), 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
for viewing Postscript files and the
Acrobat Reader for viewing and printing pdf files.
Full text versions of the paper:
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 ().
Design by Joachim Ekebom