• English
    • norsk
  • English 
    • English
    • norsk
  • 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)
Permanent link
http://hdl.handle.net/11250/227270
Issue date
2007-08
Metadata
Show full item record
Collections
  • Discussion papers (FOR) [493]
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

Privacy policy
Powered by DSpace software

Service from Unit
 

 

Browse this CollectionIssue DateAuthorsTitlesSubjectsDocument TypesJournalsBrowse ArchiveCommunities & CollectionsIssue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us

Privacy policy
Powered by DSpace software

Service from Unit