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 ${\displaystyle G=(V,E)}$ con un nodo sorgente ${\displaystyle s\in V}$ e un pozzo ${\displaystyle t\in V}$, in cui ogni arco ${\displaystyle (u,v)\in E}$ ha capacità ${\displaystyle c(u,v)>0}$, flusso ${\displaystyle f(u,v)\geq 0}$ e costo ${\displaystyle a(u,v)}$ (gli algoritmi di MCF supportano archi di costo negativo). Il costo di spedire questo flusso tramite un arco ${\displaystyle (u,v)}$ è ${\displaystyle f(u,v)\cdot a(u,v)}$. Il problema fissa un certo ammontare di flusso ${\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.

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

con i seguenti vincoli:

Vincolo di capacità: ${\displaystyle \,f(u,v)\leq c(u,v)}$

Emisimmetria: ${\displaystyle \,f(u,v)=-f(v,u)}$

Conservazione del flusso: ${\displaystyle \,\sum _{w\in V}f(u,w)=0\quad \forall u\neq s,t}$

Flusso imposto: ${\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