Busca avançada
Ano de início
Entree


Exact solution of network flow models with strong relaxations

Texto completo
Autor(es):
de Lima, Vinicius Loti ; Iori, Manuel ; Miyazawa, Flavio Keidi
Número total de Autores: 3
Tipo de documento: Artigo Científico
Fonte: MATHEMATICAL PROGRAMMING; v. 197, n. 2, p. 34-pg., 2022-03-07.
Resumo

We address the solution of Mixed Integer Linear Programming (MILP) models with strong relaxations that are derived from Dantzig-Wolfe decompositions and allow a pseudo-polynomial pricing algorithm. We exploit their network-flow characterization and provide a framework based on column generation, reduced-cost variable-fixing, and a highly asymmetric branching scheme that allows us to take advantage of the potential of the current MILP solvers. We apply our framework to a variety of cutting and packing problems from the literature. The efficiency of the framework is proved by extensive computational experiments, in which a significant number of open instances could be solved to proven optimality for the first time. (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