| Texto completo | |
| Autor(es): |
Da, Renan F. F.
;
Schouery, Rafael C. S.
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | INFORMS JOURNAL ON COMPUTING; v. N/A, p. 24-pg., 2025-10-23. |
| Resumo | |
We present a branch-cut-and-price framework to solve cutting stock problems with strong relaxations using set covering (packing) formulations, which are solved by column generation. The main contributions of this paper include an extended Ryan-Foster scheme, which allows us to use this powerful branching scheme even in nonbinary problems by using a conflict propagation lemma; a fast column generation process based on a diversification strategy; custom primal heuristics, enabling us to find optimal solutions for several open instances; and a technique to use a smaller feasibility tolerance in floatingpoint linear programming solvers, combined with numerically safe methods to produce stronger and safer lower bounds. Additional performance-improving strategies include a technique that controls the height of the branch-and-bound tree; a variable selection algorithm based on branching history; a new set of dual inequalities; insights to obtain a lean model; and the subset-row inequalities. By employing this comprehensive framework, we overcame the current state-of-the-art concerning the following problems: cutting stock, skiving stock, ordered open-end bin packing, class-constrained bin packing, and identical parallel machines scheduling with minimum makespan. Additionally, a new challenging benchmark for cutting stock is introduced. (AU) | |
| Processo FAPESP: | 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos |
| Beneficiário: | Reinaldo Morabito Neto |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |