IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v52y2004i4p623-638.html
   My bibliography  Save this article

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

Author

Listed:
  • Marc Peeters

    (Electrabel, Place de l'Université 16, 1348 Louvain-la-Neuve, Belgium)

  • Zeger Degraeve

    (London Business School, Sussex Place, Regent's Park, London NW1 4SA, United Kingdom)

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.

Suggested Citation

  • Marc Peeters & Zeger Degraeve, 2004. "The Co-Printing Problem: A Packing Problem with a Color Constraint," Operations Research, INFORMS, vol. 52(4), pages 623-638, August.
    • Handle: RePEc:inm:oropre:v:52:y:2004:i:4:p:623-638
    DOI: 10.1287/opre.1040.0112
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1040.0112
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1040.0112?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. François Vanderbeck, 2000. "On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm," Operations Research, INFORMS, vol. 48(1), pages 111-128, February.
    2. Christopher S. Tang & Eric V. Denardo, 1988. "Models Arising from a Flexible Manufacturing Machine, Part I: Minimization of the Number of Tool Switches," Operations Research, INFORMS, vol. 36(5), pages 767-777, October.
    3. Christopher S. Tang & Eric V. Denardo, 1988. "Models Arising from a Flexible Manufacturing Machine, Part II: Minimization of the Number of Switching Instants," Operations Research, INFORMS, vol. 36(5), pages 778-784, October.
    4. Vanderbeck, F. & Wolsey, L. A., 1996. "An exact algorithm for IP column generation," LIDAM Reprints CORE 1242, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Pamela H. Vance & Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser, 1997. "Airline Crew Scheduling: A New Formulation and Decomposition Algorithm," Operations Research, INFORMS, vol. 45(2), pages 188-200, April.
    6. Martin Savelsbergh, 1997. "A Branch-and-Price Algorithm for the Generalized Assignment Problem," Operations Research, INFORMS, vol. 45(6), pages 831-841, December.
    7. P. C. Gilmore & R. E. Gomory, 1961. "A Linear Programming Approach to the Cutting-Stock Problem," Operations Research, INFORMS, vol. 9(6), pages 849-859, December.
    8. Crama, Yves & Oerlemans, Alwin G., 1994. "A column generation approach to job grouping for flexible manufacturing systems," European Journal of Operational Research, Elsevier, vol. 78(1), pages 58-80, October.
    9. H. Kellerer & U. Pferschy, 1999. "Cardinality constrained bin‐packing problems," Annals of Operations Research, Springer, vol. 92(0), pages 335-348, January.
    10. Singh, N., 1993. "Design of cellular manufacturing systems: An invited review," European Journal of Operational Research, Elsevier, vol. 69(3), pages 284-291, September.
    11. Zeger Degraeve & Marc Peeters, 2003. "Optimal Integer Solutions to Industrial Cutting-Stock Problems: Part 2, Benchmark Results," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 58-81, February.
    12. Zeger Degraeve & Linus Schrage, 1999. "Optimal Integer Solutions to Industrial Cutting Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 406-419, November.
    13. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Barkel, Mathijs & Delorme, Maxence & Malaguti, Enrico & Monaci, Michele, 2025. "Bounds and heuristic algorithms for the bin packing problem with minimum color fragmentation," European Journal of Operational Research, Elsevier, vol. 320(1), pages 57-68.
    2. Saharnaz Mehrani & Carlos Cardonha & David Bergman, 2022. "Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1070-1085, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Degraeve, Z. & Jans, R.F., 2003. "A New Dantzig-Wolfe Reformulation And Branch-And-Price Algorithm For The Capacitated Lot Sizing Problem With Set Up Times," ERIM Report Series Research in Management ERS-2003-010-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    2. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    3. Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
    4. Guglielmo Lulli & Suvrajeet Sen, 2004. "A Branch-and-Price Algorithm for Multistage Stochastic Integer Programming with Application to Stochastic Batch-Sizing Problems," Management Science, INFORMS, vol. 50(6), pages 786-796, June.
    5. Peeters, Marc & Degraeve, Zeger, 2006. "Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem," European Journal of Operational Research, Elsevier, vol. 170(2), pages 416-439, April.
    6. Gamvros, Ioannis & Raghavan, S., 2012. "Multi-period traffic routing in satellite networks," European Journal of Operational Research, Elsevier, vol. 219(3), pages 738-750.
    7. Daniel Villeneuve & Jacques Desrosiers & Marco Lübbecke & François Soumis, 2005. "On Compact Formulations for Integer Programs Solved by Column Generation," Annals of Operations Research, Springer, vol. 139(1), pages 375-388, October.
    8. Zeger Degraeve & Marc Peeters, 2003. "Optimal Integer Solutions to Industrial Cutting-Stock Problems: Part 2, Benchmark Results," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 58-81, February.
    9. Richard Freling & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2003. "A Branch-and-Price Algorithm for the Multiperiod Single-Sourcing Problem," Operations Research, INFORMS, vol. 51(6), pages 922-939, December.
    10. Krzysztof C. Kiwiel, 2010. "An Inexact Bundle Approach to Cutting-Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 131-143, February.
    11. Huisman, D. & Jans, R.F. & Peeters, M. & Wagelmans, A.P.M., 2003. "Combining Column Generation and Lagrangian Relaxation," ERIM Report Series Research in Management ERS-2003-092-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    12. Lijun Wei & Zhixing Luo, & Roberto Baldacci & Andrew Lim, 2020. "A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 428-443, April.
    13. Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2016. "Bin packing and cutting stock problems: Mathematical models and exact algorithms," European Journal of Operational Research, Elsevier, vol. 255(1), pages 1-20.
    14. Valerio de Carvalho, J. M., 2002. "LP models for bin packing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 141(2), pages 253-273, September.
    15. Syam Menon & Linus Schrage, 2002. "Order Allocation for Stock Cutting in the Paper Industry," Operations Research, INFORMS, vol. 50(2), pages 324-332, April.
    16. Marjan van den Akker & Han Hoogeveen & Steef van de Velde, 2002. "Combining Column Generation and Lagrangean Relaxation to Solve a Single-Machine Common Due Date Problem," INFORMS Journal on Computing, INFORMS, vol. 14(1), pages 37-51, February.
    17. Peeters, M. & Kroon, L.G., 2003. "Circulation of Railway Rolling Stock: A Branch-and-Price Approach," ERIM Report Series Research in Management ERS-2003-055-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    18. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    19. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    20. Yves Crama & Joris van de Klundert, 1999. "Worst‐case performance of approximation algorithms for tool management problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(5), pages 445-462, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:52:y:2004:i:4:p:623-638. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.