We present a Cost Decomposition approach for the linear Multicommodity Min-Cost Flow problem, where the mutual capacity constraints are dualized and the resulting Lagrangian Dual is solved with a dual-ascent algorithm belonging to the class of Bundle methods. Although decomposition approaches to block-structured Linear Programs have been reported not to be competitive with general-purpose software, our extensive computational comparison shows that, when carefully implemented, a decomposition algorithm can outperform several other approaches, especially on problems where the number of commodities is "large" with respect to the size of the graph. Our specialized Bundle algorithm is characterized by a new heuristic for the trust region parameter handling, and embeds a specialized Quadratic Program solver that allows the efficient implementation of strategies for reducing the number of active Lagrangian variables. We also exploit the structural properties of the single-commodity Min-Cost Flow subproblems to reduce the overall computational cost. The proposed approach can be easily extended to handle variants of the problem.

A Bundle Type Dual-ascent Approach to Linear Multicommodity Min Cost Flow Problems

FRANGIONI, ANTONIO;GALLO, GIORGIO ANGELO
1999-01-01

Abstract

We present a Cost Decomposition approach for the linear Multicommodity Min-Cost Flow problem, where the mutual capacity constraints are dualized and the resulting Lagrangian Dual is solved with a dual-ascent algorithm belonging to the class of Bundle methods. Although decomposition approaches to block-structured Linear Programs have been reported not to be competitive with general-purpose software, our extensive computational comparison shows that, when carefully implemented, a decomposition algorithm can outperform several other approaches, especially on problems where the number of commodities is "large" with respect to the size of the graph. Our specialized Bundle algorithm is characterized by a new heuristic for the trust region parameter handling, and embeds a specialized Quadratic Program solver that allows the efficient implementation of strategies for reducing the number of active Lagrangian variables. We also exploit the structural properties of the single-commodity Min-Cost Flow subproblems to reduce the overall computational cost. The proposed approach can be easily extended to handle variants of the problem.
Frangioni, Antonio; Gallo, GIORGIO ANGELO
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/190502
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 69
  • ???jsp.display-item.citation.isi??? 53
social impact