The co-printing problem: a packing problem with a color constraint

The co-printing problem: a packing problem with a color constraint

0.00 Avg rating0 Votes
Article ID: iaor20073704
Country: United States
Volume: 52
Issue: 4
Start Page Number: 623
End Page Number: 638
Publication Date: Jul 2004
Journal: Operations Research
Authors: ,
Keywords: programming: integer, inventory
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.