Exact solution of bin‐packing problems using column generation and branch‐and‐bound

摘要: We explore an arc flow formulation with side constraints for the one‐dimensionalbin‐packing problem. The model has a set of conservation and ofconstraints that force appropriate number items to be included in packing. Themodel is tightened by fixing some variables at zero level, reduce symmetry thesolution space, introducing valid inequalities. solved exactly using abranch‐and‐price procedure combines deferred variable generation branch‐and‐bound.At each iteration, subproblem generates columns, which altogether correspondto attractive packing single bin. describe this subproblem, theway it modified branch‐and‐bound phase, after branching are addedto model. report computational times obtained solution bin‐packingproblems from OR‐Library test data sets. linear relaxation provides astrong lower bound bin‐packing problem leads tractable branch‐and‐boundtrees instances under consideration.