Solving Bin Packing Problems Using VRPSolver Models

Artur Pessoa (), Ruslan Sadykov () and Eduardo Uchoa ()
Additional contact information
Artur Pessoa: Universidade Federal Fluminense - Engenharia de Produção
Ruslan Sadykov: Universidade Federal Fluminense - Engenharia de Produção
Eduardo Uchoa: Inria Bordeaux – Sud-Ouest

SN Operations Research Forum, 2021, vol. 2, issue 2, 1-25

Abstract: Abstract We propose branch-cut-and-price algorithms for the classic bin packing problem and also for the following related problems: vector packing, variable sized bin packing, and variable sized bin packing with optional items. The algorithms are defined as models for VRPSolver, a generic solver for vehicle routing problems. In that way, a simple parameterization enables the use of several branch-cut-and-price advanced elements: automatic stabilization by smoothing, limited-memory rank-1 cuts, enumeration, hierarchical strong branching, and limited discrepancy search diving heuristics. As an original theoretical contribution, we prove that the branching over accumulated resource consumption (Gélinas et al, Ann Oper Res 61(1):91–109, 1995) that does not increase the difficulty of the pricing subproblem is sufficient for those bin packing models. Extensive computational results on instances from the literature show that the VRPSolver models have a performance that is very robust over all those problems, being often superior to the existing exact algorithms on the hardest instances. Several instances could be solved to optimality for the first time.

Keywords: Integer programming; Column generation; Packing (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s43069-020-00047-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:snopef:v:2:y:2021:i:2:d:10.1007_s43069-020-00047-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-020-00047-8

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

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