Scandinavian Working Papers in Business Administration

Discussion Papers,
Norwegian School of Economics, Department of Business and Management Science

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 ()
Additional contact information
David Bredström: Dept. of Mathematics, Linköping University, Postal: Linköping University, Department of Mathematics, SE-581 83 Linköping, Sweden
Kurt Jörnsten: Dept. of Finance and Management Science, Norwegian School of Economics and Business Administration, Postal: NHH , Department of Finance and Management Science, Helleveien 30, N-5045 Bergen, Norway
Mikael Rönnqvist: Dept. of Finance and Management Science, Norwegian School of Economics and Business Administration, Postal: NHH , Department of Finance and Management Science, Helleveien 30, N-5045 Bergen, Norway

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

JEL-codes: C61

15 pages, August 9, 2007

Full text files

227271 PDF-file 

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 ().

This page generated on 2024-03-14 04:36:11.