Problema del flusso di costo minimo

Il problema del flusso di costo minimo (minimum-cost flow problem, abbreviato MCFP) è un problema di decisione e ottimizzazione che consiste nel trovare il modo meno costoso possibile di far passare un certo ammontare di flusso tramite una rete di flusso.

Definizione

Una rete di flusso è un grafo orientato G = ( V , E ) {\displaystyle G=(V,E)} con un nodo sorgente s ∈ V {\displaystyle s\in V} e un pozzo t ∈ V {\displaystyle t\in V} , in cui ogni arco ( u , v ) ∈ E {\displaystyle (u,v)\in E} ha capacità c ( u , v ) > 0 {\displaystyle c(u,v)>0} , flusso f ( u , v ) ≥ 0 {\displaystyle f(u,v)\geq 0} e costo a ( u , v ) {\displaystyle a(u,v)} (gli algoritmi di MCF supportano archi di costo negativo). Il costo di spedire questo flusso tramite un arco ( u , v ) {\displaystyle (u,v)} è f ( u , v ) ⋅ a ( u , v ) {\displaystyle f(u,v)\cdot a(u,v)} . Il problema fissa un certo ammontare di flusso d {\displaystyle d} che deve essere spedito dalla sorgente al pozzo.

Il problema richiede di minimizzare il costo totale del flusso passante per tutti gli archi.

∑ ( u , v ) ∈ E a ( u , v ) ⋅ f ( u , v ) {\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}

con i seguenti vincoli:

Vincolo di capacità: f ( u , v ) ≤ c ( u , v ) {\displaystyle \,f(u,v)\leq c(u,v)}
Emisimmetria: f ( u , v ) = − f ( v , u ) {\displaystyle \,f(u,v)=-f(v,u)}
Conservazione del flusso: ∑ w ∈ V f ( u , w ) = 0 ∀ u ≠ s , t {\displaystyle \,\sum _{w\in V}f(u,w)=0\quad \forall u\neq s,t}
Flusso imposto: ∑ w ∈ V f ( s , w ) = d ∧ ∑ w ∈ V f ( w , t ) = d {\displaystyle \,\sum _{w\in V}f(s,w)=d\land \sum _{w\in V}f(w,t)=d}

Relazioni con altri problemi

Una variante del problema è quella di trovare la soluzione al problema del flusso massimo che abbia costo minimo. Può risultare utile per trovare l'accoppiamento massimo di costo minimo.

Un altro problema correlato è quello della circolazione di costo minimo, che può essere sfruttato per risolvere il MCFP.

Inoltre, i seguenti problemi possono essere considerati casi particolari：

  • rimuovendo il vincolo di capacità, il MCFP viene ridotto al problema del cammino minimo,
  • se tutti i costi vengono impostati uguali a zero, il MCFP viene ridotto al problema del flusso massimo.

Soluzioni

Il problema del flusso di costo minimo può essere risolto tramite programmazione lineare. Esistono, inoltre, molti algoritmi combinatoriali.[1] Alcuni di essi sono generalizzazioni degli algoritmi per il flusso massimo, altri utilizzano approcci completamente differenti.

Gli algoritmi più conosciuti:

  • Cycle canceling.[2]
  • Minimum mean cycle canceling: algoritmo fortemente polinomiale.[3]
  • Successive shortest path e capacity scaling: metodi che possono essere visti come generalizzazione dell'algoritmo di Ford-Fulkerson.[4]
  • Cost scaling: metodo che può essere visto come generalizzazione dell'algoritmo push-relabel.[5]
  • Algoritmo del simplesso su reti:[6] specializzazione dell'algoritmo del simplesso.[7]
  • Algoritmo out-of-kilter, ideato da D. R. Fulkerson

Note

  1. ^ (EN) Ravindra K. Ahuja, Thomas L. Magnanti e James B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Inc., 1993, ISBN 0-13-617549-X.
  2. ^ (EN) Morton Klein, A primal method for minimal cost flows with applications to the assignment and transportation problems, in Management Science, vol. 14, 1967, pp. 205–220, DOI:10.1287/mnsc.14.3.205.
  3. ^ (EN) Andrew V. Goldberg e Robert E. Tarjan, Finding minimum-cost circulations by canceling negative cycles, in Journal of the ACM, vol. 36, n. 4, 1989, pp. 873–886, DOI:10.1145/76359.76368.
  4. ^ (EN) Jack Edmonds e Richard M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, in Journal of the ACM, vol. 19, n. 2, 1972, pp. 248–264, DOI:10.1145/321694.321699.
  5. ^ (EN) Andrew V. Goldberg e Robert E. Tarjan, Finding minimum-cost circulations by successive approximation, in Math. Oper. Res., vol. 15, n. 3, 1990, pp. 430–466, DOI:10.1287/moor.15.3.430.
  6. ^ Alessandro Agnetis, Flusso a costo minimo e simplesso su reti (PDF), su dii.unisi.it, Università degli Studi di Siena, Dipartimento di Ingegneria dell'Informazione. URL consultato il 4 settembre 2016 (archiviato il 20 settembre 2010).
  7. ^ (EN) James B. Orlin, A polynomial time primal network simplex algorithm for minimum cost flows, in Mathematical Programming, vol. 78, 1997, pp. 109–129, DOI:10.1007/bf02614365.

Voci correlate

  • LEMON (C++)
  • GLPK

Collegamenti esterni

  • Marco Locatelli, Problemi di flusso a costo minimo (PDF), su di.unito.it, Università degli Studi di Torino, Dipartimento di informatica. URL consultato il 4 settembre 2016 (archiviato il 4 settembre 2016).
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica