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. - (2022), pp. 1-34. [10.1007/s10107-022-01785-9]

Exact solution of network flow models with strong relaxations

Iori M.;
2022

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.
7-mar-2022
1
34
Exact solution of network flow models with strong relaxations / de Lima, V. L.; Iori, M.; Miyazawa, F. K.. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - (2022), pp. 1-34. [10.1007/s10107-022-01785-9]
de Lima, V. L.; Iori, M.; Miyazawa, F. K.
File in questo prodotto:
File Dimensione Formato  
deLimaIoriMiyazawa2022.pdf

non disponibili

Descrizione: Articolo definitvo
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 563.17 kB
Formato Adobe PDF
563.17 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1274239
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact