Integer Programming Based Methods Applied to Cutting, Packing, and Scheduling
Resumo
We propose many contributions related to combinatorial optimization. First, we propose a number of exact methods for a general class of integer programming models, allowing applications to several important combinatorial optimization problems. To evaluate the effectiveness of our methods, we apply them to many well-studied cutting, packing, and scheduling problems, including the classical bin packing problem. The proposed methods could solve a large number of open benchmark instances, becoming the leading algorithms and the new state-of-the-art of all these problems. We also propose contributions to facilitate future research on two-dimensional cutting and packing. Lastly, we solve a complex problem arisen from a real-world case study in the food industry.
Palavras-chave:
Combinatorial Optimization, Integer Programming, Network Flow, Large-scale Optimization
Referências
American Optimization Society (2022). Bin packing and machine scheduling. https://www.ams.org/publicoutreach/feature-column/fcarc-packings3. Accessed: 2022-03-22.
Bolsi, B., de Lima, V., de Queiroz, T., and Iori, M. (2021). Integrated workforce scheduling and flexible flow shop problem in the meat industry. In Dolgui, A., Bernard, A., Lemoine, D., von Cieminski, G., and Romero, D., editors, Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems, pages 594–602. Springer.
Ceselli, A. and Righini, G. (2008). An optimization algorithm for the ordered open-end bin-packing problem. Operations Research, 56(2):425–436.
Dantzig, G. and Wolfe, P. (1961). The decomposition algorithm for linear programs. Econometrica, 29(4):767–778.
de Lima, V., Alves, C., Clautiaux, F., Iori, M., and Valério de Carvalho, J. (2022). Arc flow formulations based on dynamic programming: Theoretical foundations and applications. European Journal of Operational Research, 296(1):3–21.
de Lima, V., Iori, M., and Miyazawa, F. (2021). New exact techniques applied to a class of network flow formulations. In Singh, M. and Williamson, D., editors, Integer Programming and Combinatorial Optimization, pages 178–192. Springer.
de Lima, V., Iori, M., and Miyazawa, F. (2022). Exact solution of network flow models with strong relaxations. Mathematical Programming (forthcoming).
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. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255(1):1–20.
Eastman, W., Even, S., and Isaacs, I. (1964). Bounds for the optimal scheduling of n jobs on m processors. Management Science, 11(2):268–279.
Eliiyi, U. and Eliiyi, D. (2009). Applications of bin packing models through the supply chain. International Journal of Business and Management Studies, 1(1):11–19.
Iori, M., de Lima, V., Martello, S., Miyazawa, F., and Monaci, M. (2021). Exact solution techniques for two-dimensional cutting and packing. European Journal of Operational Research, 289(2):399–415.
Iori, M., de Lima, V., Martello, S., and Monaci, M. (2022). 2DPackLib: A twodimensional cutting and packing library. Optimization Letters, 16(2):471–480.
Kramer, A., Dell’Amico, M., and Iori, M. (2019). Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines. European Journal of Operational Research, 275(1):67–79.
Kumaraswamy, S. and Nair, M. (2019). Bin packing algorithms for virtual machine placement in cloud computing: a review. International Journal of Electrical and Computer Engineering, 9(1):512.
Martinovic, J., Delorme, M., Iori, M., Scheithauer, G., and Strasdat, N. (2020). Improved flow-based formulations for the skiving stock problem. Computers & Operations Research, 113 article 104770.
Nemhauser, G. and Wolsey, L. (1988). Integer and Combinatorial Optimization. Wiley & Sons.
Pessoa, A., Sadykov, R., Uchoa, E., and Vanderbeck, F. (2020). A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183:483–523.
Tian-Soon Lee, Y.-T. L. (2019). A review of scheduling problem and resolution methods in flexible flow shop. International Journal of Industrial Engineering Computations, 10(1):67–88.
Valério de Carvalho, J. (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86:629–659.
Vanderbeck, F. (2000). On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research, 48(1):111–128.
Vanderbeck, F. and Savelsbergh, M. (2006). A generic view of Dantzig–Wolfe decomposition in mixed integer programming. Operations Research Letters, 34(3):296–306.
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.
Bolsi, B., de Lima, V., de Queiroz, T., and Iori, M. (2021). Integrated workforce scheduling and flexible flow shop problem in the meat industry. In Dolgui, A., Bernard, A., Lemoine, D., von Cieminski, G., and Romero, D., editors, Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems, pages 594–602. Springer.
Ceselli, A. and Righini, G. (2008). An optimization algorithm for the ordered open-end bin-packing problem. Operations Research, 56(2):425–436.
Dantzig, G. and Wolfe, P. (1961). The decomposition algorithm for linear programs. Econometrica, 29(4):767–778.
de Lima, V., Alves, C., Clautiaux, F., Iori, M., and Valério de Carvalho, J. (2022). Arc flow formulations based on dynamic programming: Theoretical foundations and applications. European Journal of Operational Research, 296(1):3–21.
de Lima, V., Iori, M., and Miyazawa, F. (2021). New exact techniques applied to a class of network flow formulations. In Singh, M. and Williamson, D., editors, Integer Programming and Combinatorial Optimization, pages 178–192. Springer.
de Lima, V., Iori, M., and Miyazawa, F. (2022). Exact solution of network flow models with strong relaxations. Mathematical Programming (forthcoming).
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. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255(1):1–20.
Eastman, W., Even, S., and Isaacs, I. (1964). Bounds for the optimal scheduling of n jobs on m processors. Management Science, 11(2):268–279.
Eliiyi, U. and Eliiyi, D. (2009). Applications of bin packing models through the supply chain. International Journal of Business and Management Studies, 1(1):11–19.
Iori, M., de Lima, V., Martello, S., Miyazawa, F., and Monaci, M. (2021). Exact solution techniques for two-dimensional cutting and packing. European Journal of Operational Research, 289(2):399–415.
Iori, M., de Lima, V., Martello, S., and Monaci, M. (2022). 2DPackLib: A twodimensional cutting and packing library. Optimization Letters, 16(2):471–480.
Kramer, A., Dell’Amico, M., and Iori, M. (2019). Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines. European Journal of Operational Research, 275(1):67–79.
Kumaraswamy, S. and Nair, M. (2019). Bin packing algorithms for virtual machine placement in cloud computing: a review. International Journal of Electrical and Computer Engineering, 9(1):512.
Martinovic, J., Delorme, M., Iori, M., Scheithauer, G., and Strasdat, N. (2020). Improved flow-based formulations for the skiving stock problem. Computers & Operations Research, 113 article 104770.
Nemhauser, G. and Wolsey, L. (1988). Integer and Combinatorial Optimization. Wiley & Sons.
Pessoa, A., Sadykov, R., Uchoa, E., and Vanderbeck, F. (2020). A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183:483–523.
Tian-Soon Lee, Y.-T. L. (2019). A review of scheduling problem and resolution methods in flexible flow shop. International Journal of Industrial Engineering Computations, 10(1):67–88.
Valério de Carvalho, J. (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86:629–659.
Vanderbeck, F. (2000). On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research, 48(1):111–128.
Vanderbeck, F. and Savelsbergh, M. (2006). A generic view of Dantzig–Wolfe decomposition in mixed integer programming. Operations Research Letters, 34(3):296–306.
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.
Publicado
31/07/2022
Como Citar
LIMA, Vinícius L. de; QUEIROZ, Thiago A. de; MIYAZAWA, Flávio K..
Integer Programming Based Methods Applied to Cutting, Packing, and Scheduling. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 35. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 11-20.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2022.222639.
