| Texto completo | |
| Autor(es): |
de Lima, VInicius L.
;
Iori, Manuel
;
Miyazawa, Flavio K.
;
Singh, M
;
Williamson, DP
Número total de Autores: 5
|
| Tipo de documento: | Artigo Científico |
| Fonte: | INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2021; v. 12707, p. 15-pg., 2021-01-01. |
| Resumo | |
We propose a number of solution techniques for general network flow formulations derived from Dantzig-Wolfe decompositions. We present an arc selection method to derive reduced network flow models that may potentially provide good feasible solutions. This method is explored as a variable selection rule for branching. With the aim of improving reduced-cost variable-fixing, we also propose a method to produce different dual solutions of network flow models and provide conditions that guarantee the correctness of the method. We embed the proposed techniques in an innovative branch-and-price method for network flow formulations, and test it on the cutting stock problem. In our computational experiments, 162 out of 237 open benchmark instances are solved to proven optimality within a reasonable computational time, consistently improving previous results in the literature. (AU) | |
| 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 |
| Processo FAPESP: | 17/11831-1 - Algoritmos e modelos para problemas de corte e empacotamento |
| Beneficiário: | Vinícius Loti de Lima |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado Direto |
| Processo FAPESP: | 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, 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 |