A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems

Lijun Wei (), Zhixing Luo, (), Roberto Baldacci () and Andrew Lim ()
Additional contact information
Lijun Wei: Key Laboratory of Computer Integrated Manufacturing System, School of Electromechanical Engineering, Guangdong University of Technology, 510006 Guangzhou, People's Republic of China
Zhixing Luo,: School of Management and Engineering, Nanjing University, 210093 Nanjing, People’s Republic of China;
Roberto Baldacci: Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore 119077
Andrew Lim: Department of Electrical, Electronic, and Information Engineering "Guglielmo Marconi," University of Bologna, 47521 Cesena, Italy

INFORMS Journal on Computing, 2020, vol. 32, issue 2, 428-443

Abstract: In this paper, a new branch-and-price-and-cut algorithm is proposed to solve the one-dimensional bin-packing problem (1D-BPP). The 1D-BPP is one of the most fundamental problems in combinatorial optimization and has been extensively studied for decades. Recently, a set of new 500 test instances were proposed for the 1D-BPP, and the best exact algorithm proposed in the literature can optimally solve 167 of these new instances, with a time limit of 1 hour imposed on each execution of the algorithm. The exact algorithm proposed in this paper is based on the classical set-partitioning model for the 1DBPPs and the subset row inequalities. We describe an ad hoc label-setting algorithm to solve the pricing problem, dominance, and fathoming rules to speed up its computation and a new primal heuristic. The exact algorithm can easily handle some practical constraints, such as the incompatibility between the items, and therefore, we also apply it to solve the one-dimensional bin-packing problem with conflicts (1D-BPPC). The proposed method is tested on a large family of 1D-BPP and 1D-BPPC classes of instances. For the 1D-BPP, the proposed method can optimally solve 237 instances of the new set of difficult instances; the largest instance involves 1,003 items and bins of capacity 80,000. For the 1D-BPPC, the experiments show that the method is highly competitive with state-of-the-art methods and that it successfully closed several open 1D-BPPC instances.

Keywords: bin packing; bin packing with conflicts; branch-and-price-and-cut; exact algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0867 (application/pdf)

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:inm:orijoc:v:32:y:2020:i:2:p:428-443

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().