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

J.M. Valério de Carvalho

Annals of Operations Research, 1999, vol. 86, issue 0, 629-659

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

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018952112615 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:86:y:1999:i:0:p:629-659:10.1023/a:1018952112615

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018952112615

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().