Arcflow formulations and constraint generation frameworks for the two-bar charts packing problem

Mathijs Barkel, Maxence Delorme

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We consider the two-bar charts packing (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 non-trivial 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, both on benchmarks inspired by the literature and on 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.
Original languageEnglish
Pages (from-to)475-494
JournalINFORMS Journal on Computing
Volume35
Issue number2
DOIs
Publication statusPublished - Mar 2023

Keywords

  • Arcflow formulation
  • Bin packing
  • Constraint generation
  • Integer programming
  • Two bar charts

Fingerprint

Dive into the research topics of 'Arcflow formulations and constraint generation frameworks for the two-bar charts packing problem'. Together they form a unique fingerprint.

Cite this