Chen, Michael2015-12-162015-12-162015-08-272015-12-16http://hdl.handle.net/10315/30728Bin 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.enAuthor owns copyright, except where explicitly noted. Please contact the author directly with licensing requests.Applied mathematicsElectronic Thesis or Dissertation2015-12-16Bin Packing ProblemBranch-and-BoundColumn Generation