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.
Exact solution of network flow models with strong relaxations / de Lima, V. L.; Iori, M.; Miyazawa, F. K.. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - 197:2(2023), pp. 813-846. [10.1007/s10107-022-01785-9]
Exact solution of network flow models with strong relaxations
Iori M.;
2023
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
deLimaIoriMiyazawa2022.pdf
Accesso riservato
Descrizione: Articolo definitvo
Tipologia:
VOR - Versione pubblicata dall'editore
Dimensione
563.17 kB
Formato
Adobe PDF
|
563.17 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris