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.

New Exact Techniques Applied to a Class of Network Flow Formulations / de Lima, V. L.; Iori, M.; Miyazawa, F. K.. - 12707:(2021), pp. 178-192. ((Intervento presentato al convegno 22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021 tenutosi a Chicago nel 2021 [10.1007/978-3-030-73879-2_13].

New Exact Techniques Applied to a Class of Network Flow Formulations

Iori M.;
2021

Abstract

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.
22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021
Chicago
2021
12707
178
192
de Lima, V. L.; Iori, M.; Miyazawa, F. K.
New Exact Techniques Applied to a Class of Network Flow Formulations / de Lima, V. L.; Iori, M.; Miyazawa, F. K.. - 12707:(2021), pp. 178-192. ((Intervento presentato al convegno 22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021 tenutosi a Chicago nel 2021 [10.1007/978-3-030-73879-2_13].
File in questo prodotto:
File Dimensione Formato  
deLimaIoriMiyazawa2021.pdf

non disponibili

Descrizione: Bozza postprint
Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 282.95 kB
Formato Adobe PDF
282.95 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/1251649
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact