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-dimensional bin-packing problem. The model has a set of flow conservation constraints and a set of constraints that force the appropriate number of items to be included in the packing. The model is tightened by fixing some variables at zero level, to reduce the symmetry of the solution space, and by introducing valid inequalities. The model is solved exactly using a branch-and-price procedure that combines deferred variable generation and branch-and-bound. At each iteration, the subproblem generates a set of columns, which altogether correspond to an attractive valid packing for a single bin. We describe this subproblem, and the way it is modified in the branch-and-bound phase, after the branching constraints are added to the model. We report the computational times obtained in the solution of the bin-packing problems from the OR-Library test data sets. The linear relaxation of this model provides a strong lower bound for the bin-packing problem and leads to tractable branch-and-bound trees for the instances under consideration.