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

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

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

con i seguenti vincoli:

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

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

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

Flusso imposto: $\,\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. Alcuni di essi sono generalizzazioni degli algoritmi per il flusso massimo, altri utilizzano approcci completamente differenti.

Gli algoritmi più conosciuti:

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

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).