Show simple item record

dc.contributor.authorBredström, David
dc.contributor.authorJörnsten, Kurt
dc.contributor.authorRönnqvist, Mikael
dc.date.accessioned2014-12-15T12:18:24Z
dc.date.available2014-12-15T12:18:24Z
dc.date.issued2007-08
dc.identifier.issn1500-4066
dc.identifier.urihttp://hdl.handle.net/11250/227270
dc.description.abstractWe 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.nb_NO
dc.language.isoengnb_NO
dc.publisherFORnb_NO
dc.relation.ispartofseriesDiscussion paper;20/07
dc.titleSearching for optimal integer solutions to set partitioning problems using column generationnb_NO
dc.typeWorking papernb_NO


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record