• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • Norges Handelshøyskole
  • Department of Business and Management Science
  • Discussion papers (FOR)
  • View Item
  •   Home
  • Norges Handelshøyskole
  • Department of Business and Management Science
  • Discussion papers (FOR)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Searching for optimal integer solutions to set partitioning problems using column generation

Bredström, David; Jörnsten, Kurt; Rönnqvist, Mikael
Working paper
Thumbnail
View/Open
2007.pdf (232.9Kb)
URI
http://hdl.handle.net/11250/227270
Date
2007-08
Metadata
Show full item record
Collections
  • Discussion papers (FOR) [556]
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.
Publisher
FOR
Series
Discussion paper;20/07

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit