Busca avançada
Ano de início
Entree


New Exact Techniques Applied to a Class of Network Flow Formulations

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