Arcflow Formulations and Constraint Generation Frameworks for the Two Bar Charts Packing Problem

Mathijs Barkel () and Maxence Delorme ()
Additional contact information
Mathijs Barkel: Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands
Maxence Delorme: Department of Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands

INFORMS Journal on Computing, 2023, vol. 35, issue 2, 475-494

Abstract: We consider the two bar charts packing problem (2-BCPP), a recent combinatorial optimization problem whose aim is to pack a set of one-dimensional items into the minimum number of bins. As opposed to the well-known bin packing problem, pairs of items are grouped to form bar charts, and a solution is only feasible if the first and second items of every bar chart are packed in consecutive bins. After providing a complete picture of the connections between the 2-BCPP and other relevant packing problems, we show how we can use these connections to derive valid lower and upper bounds for the problem. We then introduce two new integer linear programming (ILP) models to solve the 2-BCPP based on a nontrivial extension of the arcflow formulation. Even though both models involve an exponential number of constraints, we show that they can be solved within a constraint generation framework. We then empirically evaluate the performance of our bounds and exact approaches against an ILP model from the literature and demonstrate the effectiveness of our techniques on both benchmarks inspired by the literature and new classes of instances that are specifically designed to be hard to solve. The outcomes of our experiments are important for the packing community because they indicate that arcflow formulations can be used to solve targeted packing problems with precedence constraints and also that some of these formulations can be solved with constraint generation.

Keywords: bin packing; two bar charts; integer programming; arcflow formulation; constraint generation (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1256 (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:35:y:2023:i:2:p:475-494

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 ().