A Branch-and-Cut-and-Price Algorithm for Cutting Stock and Related Problems
DOI:
https://doi.org/10.5753/reic.2024.4646Abstract
In this project, we introduce a branch-and-cut-and-price framework to solve the Cutting Stock Problems with strong relaxations using the Set Covering (Packing) Formulations, which are solved through column generation. We propose an extended Ryan-Foster branching scheme tailored to non-binary models, a pricing algorithm that produces convergence in a few iterations, and a variable selection technique based on branching history. These strategies are combined with subset-row cuts and custom primal heuristics to create a framework that overcomes the current state-of-the-art of Cutting Stock Problem, Skiving Stock Problem, and other related problems, being at least twice faster in the first problem and at least 60% faster in the second one.
Downloads
References
Belov, G. and 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, 171(1):85–106.
Belvaux, G. and Wolsey, L. A. (2000). bc — prod: A specialized branch-and-cut system for lot-sizing problems. Management Science, 46(5):724–738.
Delorme, M. and Iori, M. (2020). Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS Journal on Computing, 32(1):101–119.
Delorme, M., Iori, M., and Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters, 12(2):235–250.
Foster, B. A. and Ryan, D. M. (1976). An integer programming approach to the vehicle scheduling problem. Operational Research Quarterly (1970-1977), 27(2):367–384.
Gilmore, P. C. and Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6):849–859.
Irnich, S., Desaulniers, G., Desrosiers, J., and Hadjar, A. (2010). Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS Journal on Computing, 22(2):297–313.
Jepsen, M., Petersen, B., Spoorendonk, S., and Pisinger, D. (2008). Subset-row inequalities applied to the vehicle-routing problem with time windows. Operations Research, 56(2):497–511.
Korbacher, L., Irnich, S., Martinovic, J., and Strasdat, N. (2023). Solving the skiving stock problem by a combination of stabilized column generation and the reflect arcflow model. Discrete Applied Mathematics, 334:145–162.
Lima, V. L. d., Iori, M., and Miyazawa, F. K. (2023). Exact solution of network flow models with strong relaxations. Mathematical Programming, 197:813–846.
Martinovic, J., Delorme, M., Iori, M., Scheithauer, G., and Strasdat, N. (2020). Improved flow-based formulations for the skiving stock problem. Computers and Operations Research, 113:104770.
Pessoa, A., Sadykov, R., Uchoa, E., and Vanderbeck, F. (2020). A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183(1):483–523.
Valério de Carvalho, J. M. (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86:629–659.
Vance, P. H., Barnhart, C., Johnson, E. L., and Nemhauser, G. L. (1994). Solving binary cutting stock problems by column generation and branch-and-bound. Computational Optimization and Applications, 3(2):111–130.
Wei, L., Luo, Z., Baldacci, R., and Lim, A. (2020). A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS Journal on Computing, 32(2):428–443.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Authors
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
