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

• 成果类型: Article
• 署名作者: Peeters, M; Degraeve, E
• 署名单位: University of London; London Business School
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1040.0112
• 发表日期: 2004
• 页码: 623-638
• 关键词: programming; integer; algorithms : decomposition; branch-and-price; inventory/production; applications : packing

摘要

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.