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
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, http://www.nhh.no/for/cv/ronnqvist-mikael.htm

No 2007/20, Discussion Papers from Norwegian School of Economics, Department of Business and Management Science

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 (search for similar items in EconPapers)
JEL-codes: C61 (search for similar items in EconPapers)
Pages: 15 pages
Date: 2007-08-09
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/11250/227271 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://hdl.handle.net/11250/227271 [302 Found]--> https://www.unit.no/brage-denne-lenken-er-ikke-lenger-gyldig [301 Moved Permanently]--> https://sikt.no/brage-denne-lenken-er-ikke-lenger-gyldig)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhs:nhhfms:2007_020

Access Statistics for this paper

More papers in Discussion Papers from Norwegian School of Economics, Department of Business and Management Science NHH, Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway. Contact information at EDIRC.
Bibliographic data for series maintained by Stein Fossen ().