This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Peeters, M. Articles by Degraeve, Z. Search for Related Content

The Co-Printing Problem: A Packing Problem with a Color Constraint

Electrabel, Place de l'Université 16, 1348 Louvain-la-Neuve, Belgium
London Business School, Sussex Place, Regent's Park, London NW1 4SA, United Kingdom
marc.peeters2{at}electrabel.com
zdegraeve{at}london.edu

The co-printing problem is a new variant of the bin-packing problem. It finds its origin in the printing of Tetra-bricks in the beverage industry. Combining different types of bricks in one printing pattern reduces the stock. With each brick, a number of colors are associated, and the total number of colors for the whole pattern cannot exceed a given limit. We develop a branch-and-price algorithm to obtain proven optimal solutions. After introducing a Dantzig-Wolfe reformulation for the problem, we derive cutting planes to tighten the LP relaxation. We present heuristics and develop a branching scheme, avoiding complex pricing problem modifications. We present some further algorithmic enhancements, such as the implementation of dominance rules and a lower bound based on a combinatorial relaxation. Finally, we discuss computational results for real-life data sets. In addition to the introduction of a new bin-packing problem, this paper illustrates the complex balance in branch-and-price algorithms among using cutting planes, the branching scheme, and the tractability of the pricing problem. It also shows how dominance rules can be implemented in a branch-and-price framework, resulting in a substantial reduction in computation time.

Subject classifications: programming; integer; algorithms; decomposition; branch-and-price; inventory/production; applications; packing.
History: Received April 2002; revision received October 2002; revision received March 2003; revision received June 2003; accepted June 2003.