(), Kurt Jörnsten
() and Mikael Rönnqvist
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.
15 pages, August 9, 2007
Full text files
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 2018-01-23 23:36:03.