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.

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}$

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.

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

• LEMON (C++)
• GLPK

• 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