Machines. Technologies. Materials.
Vol. 19 (2025), Issue 11, pg(s) 443-447

TECHNOLOGIES

Optimizing cutting plans using duality theory: practical applications in welded pipe manufacturing

  • 1 Department of Information and Communication Technologies – The Federal State Autonomous Educational Institution of Higher Education "National Research Technological University "MISIS", Moscow, Russia

Abstract

This paper presents a practical application of the authors’ universal algorithm for optimal planning in combinatorially complex problems, using the strip cutting problem in the production of electric-welded pipes as a case study. The algorithm is based on a synthesis of duality theory and an iterative approach. It implements a mechanism for selecting or generating new promising alternatives based on dual estimates, enabling the identification of a near-globally optimal solution without exhaustive enumeration. This holds true under conditions of both complete and partial a priori determinacy of the solution set.

Keywords

References

  1. Wascher, G., Hausner, H., & Schumann, H. An improved typology of cutting and packing problems // European Journal of Operational Research. – 2007. – Т. 183, №. 3. – С. 1109–1130.
  2. Valerio de Carvalho, J. M. LP models for bin packing and cutting stock problems // European Journal of Operational Research. – 2002. – T. 141, №. 2. – С. 253–273.
  3. Delorme M., Iori M., Martello S. Fifty years of cutting and packing: A structured review // European Journal of Operational Research. – 2020. – T. 288, №. 2. – С. 386–401
  4. Kolesnikov D. N. Economic-Mathematical Methods and Models: A Textbook / D. N. Kolesnikov. – Moscow: Ekonomika, 2019. – 272 pp.
  5. Schrijver A. On the history of combinatorial optimization (till 1960) // Handbook of Discrete Optimization. – Elsevier, 2005. – С. 1–68
  6. Pisinger D., Sigurd M. The two-dimensional bin packing problem with variable bin sizes and costs // Discrete Optimization. – 2005. – T. 2, №. 2. – С. 154–167
  7. Mrad, M., & Souayah, N. An Integrated Column Generation and Heuristic Approach for the Two-Dimensional Cutting Stock Problem // Computers &

Article full text

Download PDF