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. ,, 1998. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 14(5), pages 687-698, October.
    2. 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.
    3. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(4), pages 691-705, August.
    4. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(1), pages 225-228, February.
    5. 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.
    6. 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.
    7. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(3), pages 427-432, June.
    8. 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).
    9. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(4), pages 629-637, August.
    10. 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.
    11. Martin Savelsbergh, 1997. "A Branch-and-Price Algorithm for the Generalized Assignment Problem," Operations Research, INFORMS, vol. 45(6), pages 831-841, December.
    12. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(5), pages 777-788, October.
    13. 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.
    14. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(1), pages 151-160, February.
    15. 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.
    16. H. Kellerer & U. Pferschy, 1999. "Cardinality constrained bin‐packing problems," Annals of Operations Research, Springer, vol. 92(0), pages 335-348, January.
    17. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(5), pages 879-883, October.
    18. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(6), pages 1195-1198, December.
    19. ,, 1998. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 14(3), pages 381-386, June.
    20. ,, 1998. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 14(4), pages 525-537, August.
    21. Singh, N., 1993. "Design of cellular manufacturing systems: An invited review," European Journal of Operational Research, Elsevier, vol. 69(3), pages 284-291, September.
    22. 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.
    23. ,, 1998. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 14(2), pages 285-292, April.
    24. 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.
    25. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(2), pages 411-413, April.
    26. 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.
    27. ,, 1998. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 14(1), pages 151-159, February.
    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. 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. Chein-Shan Liu & Zhuojia Fu & Chung-Lun Kuo, 2017. "Directional Method of Fundamental Solutions for Three-dimensional Laplace Equation," Journal of Mathematics Research, Canadian Center of Science and Education, vol. 9(6), pages 112-123, December.
    3. 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.
    4. Hamacher, Horst W. & Pedersen, Christian Roed & Ruzika, Stefan, 2007. "Multiple objective minimum cost flow problems: A review," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1404-1422, February.
    5. 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.
    6. Marin, Liviu & Cipu, Corina, 2017. "Non-iterative regularized MFS solution of inverse boundary value problems in linear elasticity: A numerical study," Applied Mathematics and Computation, Elsevier, vol. 293(C), pages 265-286.
    7. Krzysztof C. Kiwiel, 2010. "An Inexact Bundle Approach to Cutting-Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 131-143, February.
    8. 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.
    9. 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.
    10. B. S. C. Campello & C. T. L. S. Ghidini & A. O. C. Ayres & W. A. Oliveira, 2022. "A residual recombination heuristic for one-dimensional cutting stock problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 194-220, April.
    11. 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.
    12. Tallys H. Yunes & Arnaldo V. Moura & Cid C. de Souza, 2005. "Hybrid Column Generation Approaches for Urban Transit Crew Management Problems," Transportation Science, INFORMS, vol. 39(2), pages 273-288, May.
    13. Kazuhiro Takimoto, 2021. "Precise blowup rate near the boundary of boundary blowup solutions to k-Hessian equation," Partial Differential Equations and Applications, Springer, vol. 2(1), pages 1-10, February.
    14. Albizuri, M.J. & Leroux, J. & Zarzuelo, J.M., 2010. "Updating claims in bankruptcy problems," Mathematical Social Sciences, Elsevier, vol. 60(2), pages 144-148, September.
    15. Mingue SUn, 2010. "A Branch-and-Bound Algorithm for Representative Integer Efficient Solutions in Multiple Objective Network Programming Problems," Working Papers 0007, College of Business, University of Texas at San Antonio.
    16. Amit K. Verma & Biswajit Pandit & Lajja Verma & Ravi P. Agarwal, 2020. "A Review on a Class of Second Order Nonlinear Singular BVPs," Mathematics, MDPI, vol. 8(7), pages 1-50, June.
    17. Hovik A. Matevossian, 2020. "Asymptotics and Uniqueness of Solutions of the Elasticity System with the Mixed Dirichlet–Robin Boundary Conditions," Mathematics, MDPI, vol. 8(12), pages 1-32, December.
    18. Alves, Carlos J.S. & Valtchev, Svilen S., 2018. "On the application of the method of fundamental solutions to boundary value problems with jump discontinuities," Applied Mathematics and Computation, Elsevier, vol. 320(C), pages 61-74.
    19. Wong, Patricia J.Y., 2015. "Eigenvalues of a general class of boundary value problem with derivative-dependent nonlinearity," Applied Mathematics and Computation, Elsevier, vol. 259(C), pages 908-930.
    20. 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.

    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.