Lezione 12.2: provare a risolvere un problema di flusso di costo minimo
Aggregazione dei criteri
Il problema del flusso di costo minimo: determinare una soluzione ammissibile [p. 78]. Come rendere ammissibile un'istanza inammissibile = flusso massimo con parametri (capacità sugli archi), il ruolo dei tagli di capacità minima multipli. Esecuzione dell'algoritmo per cancellazione di cicli senza averlo definito. Costruzione del flusso iniziale (flusso massimo) che usa "cattivi" cammini, sostituire un cammino "cattivo" con uno "buono" = inviare flusso lungo cicli aumentanti di costo negativo. Ciò che rimane da capire: siamo sicuri che non esistano più cicli aumentanti di costo negativo? E questo vuol dire che il flusso è ottimo? [p. 82].