IDEAS home Printed from https://ideas.repec.org/a/spr/orspec/v43y2021i1d10.1007_s00291-020-00610-z.html
   My bibliography  Save this article

Column generation algorithms for mother plate design in steel plants

Author

Listed:
  • Qi Zhang

    (Northeastern University)

  • Shixin Liu

    (Northeastern University)

  • Ruiyou Zhang

    (Northeastern University)

  • Shujin Qin

    (Northeastern University)

Abstract

This paper investigates the mother plate design (MPD) problem which is a typical problem in the production planning of steel plants. The MPD problem refers to a variant of the two-dimensional variable-sized bin packing problem in which the height of a bin is in a given finite set and the width of each bin is continuous in an interval. The problem is first formulated as a mixed integer nonlinear programming model and then linearized into a mixed integer programming model. We present a column generation-based (CG-based) algorithm to approximately solve the MPD problem, in which a height combination scheme is devised to decrease the dimensions of the pricing sub-problem. We present an accelerated CG (ACG) algorithm with improved performance which adopts two heuristic accelerating strategies in the pricing process. We use practical instances collected from a Chinese steel plant to test the performance of the proposed algorithms. The results indicate that the ACG algorithm is suitable for solving real-world instances.

Suggested Citation

  • Qi Zhang & Shixin Liu & Ruiyou Zhang & Shujin Qin, 2021. "Column generation algorithms for mother plate design in steel plants," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 127-153, March.
    • Handle: RePEc:spr:orspec:v:43:y:2021:i:1:d:10.1007_s00291-020-00610-z
    DOI: 10.1007/s00291-020-00610-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00291-020-00610-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00291-020-00610-z?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(4), pages 691-705, August.
    2. Andrea Lodi & Silvano Martello & Daniele Vigo, 1999. "Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 345-357, November.
    3. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(5), pages 879-883, October.
    4. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(6), pages 1195-1198, December.
    5. Cintra, G.F. & Miyazawa, F.K. & Wakabayashi, Y. & Xavier, E.C., 2008. "Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation," European Journal of Operational Research, Elsevier, vol. 191(1), pages 61-85, November.
    6. 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.
    7. Alves, Claudio & Valerio de Carvalho, J.M., 2007. "Accelerating column generation for variable sized bin-packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1333-1352, December.
    8. Silvano Martello & Daniele Vigo, 1998. "Exact Solution of the Two-Dimensional Finite Bin Packing Problem," Management Science, INFORMS, vol. 44(3), pages 388-399, March.
    9. Ortmann, Frank G. & Ntene, Nthabiseng & van Vuuren, Jan H., 2010. "New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems," European Journal of Operational Research, Elsevier, vol. 203(2), pages 306-315, June.
    10. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(1), pages 225-228, February.
    11. Belov, G. & Scheithauer, G., 2002. "A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths," European Journal of Operational Research, Elsevier, vol. 141(2), pages 274-294, September.
    12. P. C. Gilmore & R. E. Gomory, 1963. "A Linear Programming Approach to the Cutting Stock Problem---Part II," Operations Research, INFORMS, vol. 11(6), pages 863-888, December.
    13. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(2), pages 411-413, April.
    14. Furini, Fabio & Malaguti, Enrico & Medina Durán, Rosa & Persiani, Alfredo & Toth, Paolo, 2012. "A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size," European Journal of Operational Research, Elsevier, vol. 218(1), pages 251-260.
    15. Hong, Shaohui & Zhang, Defu & Lau, Hoong Chuin & Zeng, XiangXiang & Si, Yain-Whar, 2014. "A hybrid heuristic algorithm for the 2D variable-sized bin packing problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 95-103.
    16. Lodi, Andrea & Martello, Silvano & Monaci, Michele, 2002. "Two-dimensional packing problems: A survey," European Journal of Operational Research, Elsevier, vol. 141(2), pages 241-252, September.
    17. Kang, Jangha & Park, Sungsoo, 2003. "Algorithms for the variable sized bin packing problem," European Journal of Operational Research, Elsevier, vol. 147(2), pages 365-372, June.
    Full references (including those not matched with items on IDEAS)

    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. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    2. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    3. Krzysztof C. Kiwiel, 2010. "An Inexact Bundle Approach to Cutting-Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 131-143, February.
    4. 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.
    5. Belov, G. & Scheithauer, G., 2006. "A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting," European Journal of Operational Research, Elsevier, vol. 171(1), pages 85-106, May.
    6. Alves, Claudio & Valerio de Carvalho, J.M., 2007. "Accelerating column generation for variable sized bin-packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1333-1352, December.
    7. 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.
    8. Tao Wu & Kerem Akartunal? & Raf Jans & Zhe Liang, 2017. "Progressive Selection Method for the Coupled Lot-Sizing and Cutting-Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 523-543, August.
    9. Gleb Belov & Guntram Scheithauer, 2007. "Setup and Open-Stacks Minimization in One-Dimensional Stock Cutting," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 27-35, February.
    10. 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.
    11. Reinertsen, Harald & Vossen, Thomas W.M., 2010. "The one-dimensional cutting stock problem with due dates," European Journal of Operational Research, Elsevier, vol. 201(3), pages 701-711, March.
    12. Tao Wu & Zhe Liang & Canrong Zhang, 2018. "Analytics Branching and Selection for the Capacitated Multi-Item Lot Sizing Problem with Nonidentical Machines," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 236-258, May.
    13. 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.
    14. 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.
    15. 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.
    16. Silvio Alexandre de Araujo & Bert De Reyck & Zeger Degraeve & Ioannis Fragkos & Raf Jans, 2015. "Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 27(3), pages 431-448, August.
    17. 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.
    18. Ioannis Fragkos & Zeger Degraeve & Bert De Reyck, 2016. "A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 465-482, August.
    19. Zeger Degraeve & Raf Jans, 2007. "A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot-Sizing Problem with Setup Times," Operations Research, INFORMS, vol. 55(5), pages 909-920, October.
    20. 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.

    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:spr:orspec:v:43:y:2021:i:1:d:10.1007_s00291-020-00610-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.