Relaxations and exact solution of the variable sized bin packing problem
dc.contributor.author | Haouari, Mohamed | |
dc.contributor.author | Serairi, M. | |
dc.date.accessioned | 2012-05-31T12:56:54Z | |
dc.date.available | 2012-05-31T12:56:54Z | |
dc.date.issued | 2011-03 | |
dc.identifier.issn | 0926-6003 | |
dc.identifier.uri | http://hdl.handle.net/10679/191 | |
dc.identifier.uri | http://www.springerlink.com/content/x0p34406038n4j66/ | |
dc.description | Due to copyright restrictions, the access to the full text of this article is only available via subscription. | |
dc.description.abstract | We address a generalization of the classical one-dimensional bin packing problem with unequal bin sizes and costs. We investigate lower bounds for this problem as well as exact algorithms. The main contribution of this paper is to show that embedding a tight network flow-based lower bound, dominance rules, as well as an effective knapsack-based heuristic in a branch-and-bound algorithm yields very good performance. In addition, we show that the particular case with all weight items larger than a third the largest bin capacity can be restated and solved in polynomial-time as a maximum-weight matching problem in a nonbipartite graph. We report the results of extensive computational experiments that provide evidence that large randomly generated instances are optimally solved within moderate CPU times. | en_US |
dc.description.sponsorship | Fatimah Alnijris’ Research Chair for Advanced Manufacturing Technology | |
dc.language.iso | eng | en_US |
dc.publisher | Springer Science+Business Media | en_US |
dc.relation.ispartof | Computational Optimization and Application | |
dc.rights | restrictedAccess | |
dc.title | Relaxations and exact solution of the variable sized bin packing problem | en_US |
dc.type | Article | en_US |
dc.peerreviewed | yes | en_US |
dc.publicationstatus | published | en_US |
dc.contributor.department | Özyeğin University | |
dc.contributor.authorID | (ORCID 0000-0003-0767-8220 & YÖK ID ) Haouari, Mohamed | |
dc.contributor.ozuauthor | Haouari, Mohamed | |
dc.identifier.volume | 48 | |
dc.identifier.issue | 2 | |
dc.identifier.startpage | 345 | |
dc.identifier.endpage | 368 | |
dc.identifier.wos | WOS:000288551600010 | |
dc.identifier.doi | 10.1007/s10589-009-9276-z | |
dc.subject.keywords | Bin packing problem | en_US |
dc.subject.keywords | Lower bounds | en_US |
dc.subject.keywords | Branch-and-bound | en_US |
dc.identifier.scopus | SCOPUS:2-s2.0-79956138692 | |
dc.contributor.authorMale | 1 | |
dc.relation.publicationcategory | Article - International Refereed Journal - Institutional Academic Staff |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
Share this page