Quick Reference Cheatsheet
Formule, condizioni e scelte operative per il ripasso
OPERATIONS RESEARCH · QUICK REFERENCE
Cheatsheet del corso
Una guida compatta per riconoscere il problema, scegliere lo strumento giusto e controllare le condizioni che rendono valida la soluzione.
Forme di riferimento
Forma canonica (max)
\[ \max\ c^\top x \qquad \text{s.t. } Ax\le b,\quad x\ge0. \]
Il duale canonico è immediato:
\[ \min\ b^\top y \qquad \text{s.t. } A^\top y\ge c,\quad y\ge0. \]
Forma standard
\[ \max\ c^\top x \qquad \text{s.t. } Ax=b,\quad x\ge0. \]
Conversioni:
- \(a^\top x\le b\): aggiungi slack \(s\ge0\);
- \(a^\top x\ge b\): sottrai surplus \(s\ge0\);
- \(x_j\) libera: \(x_j=x_j^+-x_j^-\), con \(x_j^\pm\ge0\);
- \(\min f(x)=\max[-f(x)]\).
Base, BFS e costi ridotti
Per una base \(B\) con matrice \(A_B\) invertibile:
\[ \bar b=A_B^{-1}b,\qquad x_B=\bar b-A_B^{-1}A_Nx_N. \]
La soluzione di base è ammissibile (BFS) se \(\bar b\ge0\). Per ogni variabile non di base \(x_j\):
\[ \hat c_j=c_j-c_B^\top A_B^{-1}A_j, \qquad z=\bar z+\sum_{j\in N}\hat c_jx_j. \]
Per un problema di massimizzazione nella convenzione del corso:
| Controllo | Conclusione / azione |
|---|---|
| \(\hat c_j\le0\) per ogni \(j\in N\) | BFS ottima |
| esiste \(\hat c_j>0\) | \(x_j\) può entrare in base |
| \(A_B^{-1}A_j\le0\) componente per componente | problema illimitato |
| qualche \(\bar a_{ij}>0\) | applica il ratio test |
\[ \theta^*= \min_{i:\bar a_{ij}>0}\frac{\bar b_i}{\bar a_{ij}}. \]
La riga che realizza il minimo determina la variabile uscente. Se il minimo è \(0\), il pivot è degenere.
Regole di pivot e Fase I
- Dantzig: entra un indice con costo ridotto positivo massimo.
- Bland: tra gli indici ammissibili scegli il più piccolo; nel ratio test, a parità, esce la variabile di base con indice più piccolo.
- Fase I: minimizza la somma delle artificiali (o massimizza il suo opposto). Ottimo \(>0\) significa che l’LP originale è inammissibile.
- Fase II: elimina le artificiali e ripristina l’obiettivo originale.
Tre esiti da distinguere
| Esito | Significato |
|---|---|
| Inammissibile | non esiste \(x\) che soddisfa tutti i vincoli |
| Illimitato | esistono soluzioni ammissibili con valore arbitrariamente migliore |
| Ottimo multiplo | all’ottimo esiste un non-base con \(\hat c_j=0\) che ammette pivot |
Corrispondenza primale-duale
Per un primale di massimizzazione, il duale è di minimizzazione. Ogni vincolo primale genera una variabile duale; ogni variabile primale genera un vincolo duale.
| Primale max | Duale min |
|---|---|
| vincolo \(\le\) | \(y_i\ge0\) |
| vincolo \(=\) | \(y_i\) libera |
| vincolo \(\ge\) | \(y_i\le0\) |
| variabile \(x_j\ge0\) | vincolo duale \(\ge\) |
| variabile \(x_j\) libera | vincolo duale \(=\) |
| variabile \(x_j\le0\) | vincolo duale \(\le\) |
Certificati di ottimalità
Per il pair canonico max/min:
\[ c^\top x\le b^\top y \qquad\text{(dualità debole).} \]
Se \(x\) e \(y\) sono ammissibili e \(c^\top x=b^\top y\), entrambi sono ottimi (dualità forte). Equivalentemente, devono valere le condizioni di complementarità:
\[ y_i\bigl(b_i-a_i^\top x\bigr)=0\quad\forall i, \qquad x_j\bigl(a_j^\top y-c_j\bigr)=0\quad\forall j. \]
Quindi:
- \(y_i>0 \Rightarrow\) il vincolo primale \(i\) è saturo;
- \(x_j>0 \Rightarrow\) il vincolo duale \(j\) è saturo;
- slack positivo \(\Rightarrow\) il moltiplicatore corrispondente è zero.
Modellazione binaria
Siano \(y,y_A,y_B\in\{0,1\}\) e sia \(M\) un bound valido e il più stretto possibile.
| Logica | Formulazione |
|---|---|
| \(A\Rightarrow B\) | \(y_A\le y_B\) |
| almeno uno | \(\sum_j y_j\ge1\) |
| al più uno | \(\sum_j y_j\le1\) |
| esattamente uno | \(\sum_j y_j=1\) |
| \(x\) attiva solo se \(y=1\) | \(0\le x\le Uy\) |
| \(y=1\Rightarrow a^\top x\le b\) | \(a^\top x\le b+M(1-y)\) |
| \(y=0\Rightarrow a^\top x\le b\) | \(a^\top x\le b+My\) |
Either-or: almeno uno tra \(a^\top x\le b\) e \(d^\top x\le e\):
\[ a^\top x\le b+My,\qquad d^\top x\le e+M(1-y). \]
Branch-and-Bound e tagli
Per un ILP di massimizzazione, la rilassata LP fornisce un upper bound. Un nodo si chiude se:
- la rilassata è inammissibile;
- l’ottimo LP è intero (aggiorna l’incumbent);
- il bound LP non supera il valore dell’incumbent.
Se \(x_j^*\) è frazionario, crea i figli \(x_j\le\lfloor x_j^*\rfloor\) e \(x_j\ge\lceil x_j^*\rceil\). Un taglio valido elimina la soluzione LP corrente senza eliminare alcuna soluzione intera ammissibile.
Total unimodularity
\(A\) è totalmente unimodulare (TUM) se ogni sottomatrice quadrata ha determinante in \(\{-1,0,1\}\).
Se \(A\) è TUM e \(b\) è intero, tutti i vertici di
\[ P=\{x\ge0:Ax\le b\} \]
sono interi. La rilassata LP risolve quindi l’ILP.
Criterio di Ghouila-Houri. Per ogni sottoinsieme \(R\) di righe deve esistere una partizione \(R=R_1\mathbin{\dot\cup}R_2\) tale che, per ogni colonna \(j\),
\[ \sum_{i\in R_1}a_{ij}-\sum_{i\in R_2}a_{ij}\in\{-1,0,1\}. \]
Scorciatoia usata nel corso. Se ogni colonna ha al più due elementi non nulli, basta una partizione delle righe in cui:
- segni uguali \(\Rightarrow\) righe in parti diverse;
- segni opposti \(\Rightarrow\) righe nella stessa parte.
Classi da riconoscere:
- incidenza nodo-arco di un grafo diretto: TUM;
- incidenza vertice-arco di un grafo bipartito: TUM;
- aggiungere/cambiare segno/permutare righe o colonne preserva la TUM;
- l’incidenza di un triangolo non è TUM (compare un determinante \(\pm2\)).
Rappresentazioni e visite
| Struttura / algoritmo | Tempo | Uso principale |
|---|---|---|
| lista di adiacenza | spazio \(O(V+E)\) | grafi sparsi, scansione vicini |
| matrice di adiacenza | spazio \(O(V^2)\) | test arco in \(O(1)\) |
| BFS | \(O(V+E)\) | distanze con archi unitari, componenti |
| DFS | \(O(V+E)\) | cicli, SCC, ordinamento topologico |
| Kahn / DFS topologico | \(O(V+E)\) | solo DAG |
| Warshall | \(O(V^3)\) | chiusura transitiva |
Un grafo diretto è un DAG se e solo se ammette un ordinamento topologico. In DFS, la presenza di un back edge certifica un ciclo diretto.
Minimum Spanning Tree
Per un grafo non orientato, connesso e pesato:
- un albero ricoprente ha esattamente \(|V|-1\) archi;
- cut property: un arco di peso minimo che attraversa un taglio è safe (appartiene ad almeno un MST);
- cycle property: un arco strettamente più pesante in un ciclo non appartiene ad alcun MST.
| Algoritmo | Idea | Tempo tipico |
|---|---|---|
| Kruskal | ordina gli archi; aggiungi se unisce componenti diverse | \(O(E\log E)\) |
| Prim | espandi un solo albero col minimo arco uscente | \(O(E+V\log V)\) |
Pesi negativi sono ammessi. Se tutti i pesi degli archi sono distinti, l’MST è unico; il contrario non è necessario.
Operazione fondamentale: relax
Per un arco \((u,v)\) di costo \(w(u,v)\):
\[ \text{se }d[v]>d[u]+w(u,v), \quad d[v]\leftarrow d[u]+w(u,v), \quad \pi[v]\leftarrow u. \]
Le distanze finali danno i valori; i predecessori \(\pi\) ricostruiscono i cammini.
Quale algoritmo scelgo?
| Caso | Algoritmo | Complessità |
|---|---|---|
| pesi tutti uguali / non pesato | BFS | \(O(V+E)\) |
| DAG, anche con pesi negativi | ordine topologico + relax | \(O(V+E)\) |
| pesi non negativi | Dijkstra | \(O((V+E)\log V)\) con heap binario |
| pesi negativi, no ciclo negativo raggiungibile | Bellman-Ford | \(O(VE)\) |
| tutte le coppie, grafo denso | Floyd-Warshall | \(O(V^3)\) |
Dijkstra: quando un vertice è estratto con distanza minima, la sua distanza diventa definitiva. Questa proprietà richiede \(w(e)\ge0\).
Bellman-Ford: rilassa tutti gli archi per \(|V|-1\) passate. Se un arco è ancora rilassabile alla passata \(|V|\), esiste un ciclo negativo raggiungibile dalla sorgente.
DAG shortest paths: ordina topologicamente e rilassa gli archi in quell’ordine. Non serve alcuna ipotesi sul segno dei pesi.
Floyd-Warshall
Definisci \(D_{ij}^{(k)}\) come il costo minimo da \(i\) a \(j\) usando come nodi interni solo \(\{1,\ldots,k\}\):
\[ D_{ij}^{(k)} = \min\left\{ D_{ij}^{(k-1)}, D_{ik}^{(k-1)}+D_{kj}^{(k-1)} \right\}. \]
Inizializza \(D_{ii}=0\), \(D_{ij}=w(i,j)\) se l’arco esiste, \(+\infty\) altrimenti. Alla fine, \(D_{ii}<0\) segnala un ciclo negativo raggiungibile da \(i\) e che può tornare a \(i\).
Flusso ammissibile
Per ogni arco \((u,v)\):
\[ 0\le f(u,v)\le c(u,v). \]
Per ogni nodo interno \(v\notin\{s,t\}\):
\[ \sum_{u}f(u,v)=\sum_{w}f(v,w). \]
Il valore è il flusso netto uscente da \(s\). Nel residuo:
\[ c_f(u,v)=c(u,v)-f(u,v), \qquad c_f(v,u)=f(u,v). \]
Se \(P\) è un cammino aumentante,
\[ \Delta=\min_{e\in P}c_f(e), \]
poi aumenta il flusso sugli archi forward e lo diminuisce sugli archi backward.
Max-flow / min-cut
Per un cut \((S,T)\) con \(s\in S\), \(t\in T\):
\[ c(S,T)=\sum_{u\in S,\ v\in T}c(u,v), \qquad |f|\le c(S,T). \]
Quando il residuo non contiene un cammino \(s\)-\(t\), i nodi raggiungibili da \(s\) definiscono un cut di capacità \(|f|\). Questo certifica:
\[ \max |f|=\min c(S,T). \]
| Algoritmo | Scelta cammino | Complessità |
|---|---|---|
| Ford-Fulkerson | arbitraria | \(O(E|f^*|)\) con capacità intere |
| Edmonds-Karp | BFS nel residuo | \(O(VE^2)\) |
Con capacità intere esiste un massimo flusso intero.
Matching
Un matching \(M\) è un insieme di archi senza estremi condivisi.
- Cammino alternante: alterna archi fuori/dentro \(M\).
- Cammino aumentante: alternante, con estremi liberi.
- Berge: \(M\) è massimo se e solo se non esiste un cammino aumentante.
- Hall: un bipartito \(G=(L\cup R,E)\) ha un matching che copre \(L\) se e solo se \(|N(S)|\ge|S|\) per ogni \(S\subseteq L\).
- Kőnig: in un grafo bipartito, \(\lvert M_{\max}\rvert=\lvert C_{\min}\rvert\) (minimum vertex cover).
Riduzione matching \(\rightarrow\) max-flow
Costruisci:
\[ s\to L,\qquad L\to R,\qquad R\to t \]
con capacità \(1\) su tutti gli archi. Un flusso intero di valore \(k\) corrisponde a un matching di cardinalità \(k\).
Certificato di massimo flusso
Un flusso ammissibile e un cut con lo stesso valore/capacità.
Certificato di matching massimo
Assenza di cammini aumentanti; nel bipartito, anche un vertex cover della stessa cardinalità.