A Branch-and-Price Algorithm for Bin Packing Problem

Simple item page
dc.contributor.advisorChen, Michael
dc.creatorAtaei, Masoud
dc.date.accessioned2015-12-16T19:28:16Z
dc.date.available2015-12-16T19:28:16Z
dc.date.copyright2015-08-27
dc.date.issued2015-12-16
dc.date.updated2015-12-16T19:28:16Z
dc.degree.disciplineApplied and Industrial Mathematics
dc.degree.levelMaster's
dc.degree.nameMSc - Master of Science
dc.description.abstractBin Packing Problem examines the minimum number of identical bins needed to pack a set of items of various sizes. Employing branch-and-bound and column generation usually requires designation of the problem-specific branching rules compatible with the nature of the pricing sub-problem of column generation, or alternatively it requires determination of the k-best solutions of knapsack problem at level kth of the tree. Instead, we present a new approach to deal with the pricing sub-problem of column generation which handles two-dimensional knapsack problems. Furthermore, a set of new upper bounds for Bin Packing Problem is introduced in this work which employs solutions of the continuous relaxation of the set-covering formulation of Bin Packing Problem. These high quality upper bounds are computed inexpensively and dominate the ones generated by state-of-the-art methods.
dc.identifier.urihttp://hdl.handle.net/10315/30728
dc.language.isoen
dc.rightsAuthor owns copyright, except where explicitly noted. Please contact the author directly with licensing requests.
dc.subjectApplied mathematics
dc.subject.keywordsBin Packing Problem
dc.subject.keywordsBranch-and-Bound
dc.subject.keywordsColumn Generation
dc.titleA Branch-and-Price Algorithm for Bin Packing Problem
dc.typeElectronic Thesis or Dissertation

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Ataei_Masoud_2015_Masters.pdf
Size:
2.85 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
license.txt
Size:
1.83 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
YorkU_ETDlicense.txt
Size:
3.38 KB
Format:
Plain Text
Description:
Download

Collections

Applied & Industrial Mathematics

All items in the YorkSpace institutional repository are protected by copyright, with all rights reserved except where explicitly noted.