Scandinavian Working Papers in Economics
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
- Norwegian School of Economics, Department of Business and Management Science
- Ordering Working Papers
- Home page for this series
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 ().
RePEc:hhs:nhhfms:2007_020This page generated on 2024-09-13 22:16:22.