Complessit`a della Programmazione Lineare

Come visto nel Capitolo 3, il metodo del simplesso (con l’applicazione delle sue due fasi e l’utilizzo di una regola di pivot anti-ciclaggio, come ad esempio quella di Bland) `e un algoritmo per il problema della programmazione lineare. `E naturale chiedersi se tale algoritmo sia polinomiale.

Restringendoci alla sola Fase II, possiamo dividere lo studio della complessit`a del metodo del simplesso in due parti: l’esecuzione di una singola iterazione, che prende in input una base ammissibile ed il tableau relativo, sceglie le variabili da far entrare in base ed uscire dalla base, effettua il cambio di base e costruisce il nuovo tableau; e il numero di iterazioni effettuate dall’algoritmo, pari al numero di cambi di base da effettuare per raggiungere l’ottimo (o concludere che l’ottimo non esiste) partendo da una prima base ammissibile.

Osservazione 5.9 Una singola iterazione del metodo del simplesso pu`o essere eseguita in tempo polinomiale nella grandezza dell’istanza.

Dimostrazione. Per scegliere l’indice k che entra in base, basta scorrere in ordine le componenti del vettore ¯c_N fino ad individuare la prima componente ¯c_k>0 (se tale componente non esiste, abbiamo trovato la soluzione ottima): questo richiede meno di n confronti tra numeri. Per scegliere la variabile che esce di base (o concludere che il problema `e illimitato), `e sufficiente calcolare e confrontare tra loro al massimo m rapporti. L’operazione di pivot consiste nel calcolare le nuove componenti del tableau; le componenti da calcolare sono al massimo(m + 1)(n + 1) e per ciascuna di esse `e sufficiente un numero costante di operazioni elementari (si vedano le formule della Sezione 3.4). Nel complesso, il numero di operazioni elementari eseguite durante una singola iterazione `e polinomiale nella grandezza dell’istanza. ◻ Per l’osservazione precedente, se l’algoritmo del simplesso eseguisse per ogni istanza I un numero di iterazioni polinomiale in size(I), allora la sua complessit`a sarebbe polinomiale.

Poich´e il numero di iterazioni dipende dalla scelta delle variabili da far entrare in base ed uscire dalla base, la polinomialit`a potrebbe dipendere dalla regola di pivot utilizzata. Oltre alla regola di Bland, esistono altre regole che garantiscono che l’algoritmo termini in un numero finito di iterazioni. Tuttavia, per tutte le regole di pivot finora proposte sono stati trovati esempi che mostrano che il metodo del simplesso con tale regola pu`o richiedere un numero di iterazioni dell’ordine di 2ⁿ o 2^√n (dove n `e il numero di variabili del problema), dunque un numero di iterazioni che non pu`o essere limitato da alcun polinomio in size(I).

Il primo esempio in questo senso venne proposto da Klee e Minty nel 1972 per mostrare che la regola di Bland non garantisce la polinomialit`a dell’algoritmo. Un recente esempio di questo tipo, valido per un’altra particolare regola di pivot, `e datato 2011. A tutt’oggi non `e noto se esista una regola di pivot che garantisca la polinomialit`a del metodo del simplesso;

ciononostante, il comportamento dell’algoritmo nella pratica `e piuttosto soddisfacente.

Mentre la questione della polinomialit`a del metodo del simplesso `e ancora irrisolta e rap-presenta una dei problemi aperti pi`u importanti della teoria dell’ottimizzazione, esistono invece altri algoritmi polinomiali per la risoluzione di problemi di programmazione lineare.

In effetti, l’esistenza di un tale algoritmo `e rimasta una questione aperta per decenni, fino a quando nel 1979 Khachiyan trov`o il primo algoritmo polinomiale per la programmazione lineare, noto come metodo dell’ellissoide. A dispetto del suo interesse teorico, il metodo di Khachiyan non `e tuttavia efficiente in pratica. Si dovette attendere l’avvento dei cosiddetti metodi di punto interno (primi anni ’90) per avere algoritmi per la programmazione lineare

5.2. COMPLESSIT `A DEGLI ALGORITMI 61 che fossero efficienti sia in teoria (cio`e che fossero polinomiali) che nella pratica. I solutori commerciali di problemi di programmazione lineare fanno in genere uso del metodo del sim-plesso (primale o duale) e dei metodi di punto interno, a seconda del particolare problema in esame (o di un’eventuale richiesta specifica da parte dell’utente).

Capitolo 6

Problemi di Cammino Minimo

Dato un grafo orientato D =(V,A), diciamo che sono specificati costi sugli archi di D se `e assegnato un valore ce per ogni e ∈ A. Dato un sottoinsieme di archi S ⊆ A, chiamiamo costo di S il numero c(S) = ∑^e∈Sc_e.

Il problema del cammino minimo `e il seguente: dati un grafo orientato D =(V,A) con costi (c<sup>e</sup>)<sup>e∈A</sup> sugli archi ed un nodo s ∈ V (detto sorgente), trovare, per ogni v ∈ V , un cammino orientato di costo minimo da s a v (o stabilire che non c’`e alcun cammino orientato da s a v).¹

Nel resto del capitolo lavoreremo sempre con cammini e cicli orientati. Pertanto, spesso diremo semplicemente “cammino” o “ciclo” invece di “cammino orientato” e “ciclo orientato”.

Un cammino minimo da s a v `e un cammino di costo minimo da s a v.

Se non si impone alcuna condizione sui costi, non `e noto alcun algoritmo polinomiale per risolvere il problema del cammino minimo. Si pu`o dimostrare che se esistesse un tale algorit-mo, allora potremmo risolvere in tempo polinomiale anche il problema del ciclo hamiltoniano su un qualunque grafo (Esempio 5.8), cosa che, come detto nel capitolo precedente, `e ritenuta molto improbabile a causa di profonde motivazioni teoriche.

Per vedere come un eventuale algoritmo polinomiale per il problema del cammino minimo potrebbe essere usato per risolvere il problema del ciclo hamiltoniano, procediamo come segue.

Supponiamo che esista un tale algoritmo A per il problema del cammino minimo e sia G = (V,E) una qualunque istanza del problema del ciclo hamiltoniano, che vogliamo risolvere.

Scegliamo arbitrariamente un nodo s ∈ V . Si noti che se esiste un ciclo hamiltoniano in G, allora tale ciclo contiene almeno uno spigolo e ∈ δ(s) (in realt`a ne contiene esattamente due).

Allora, per decidere se G ha un ciclo hamiltoniano, `e sufficiente verificare, per ogni e ∈ δ(s), se G ha un ciclo hamiltoniano contenente lo spigolo e. Fissato uno spigolo e ∈ δ(s), diciamo e = st, facciamo quanto segue: rimuoviamo e da G, ottenendo un nuovo grafo G<sup>′</sup>; costruiamo un grafo orientato D a partire da G<sup>′</sup>, sostituendo ogni spigolo uv ∈ E con una coppia di archi opposti (u,v),(v,u); diamo costo −1 a tutti gli archi di D. Poich´e un cammino non pu`o visitare due volte lo stesso nodo, ogni cammino in D ha al massimo n − 1 archi (dove n `e il numero di nodi del grafo), dunque il costo di un cammino minimo da s a t `e sempre almeno

−(n − 1); inoltre, tale costo `e esattamente −(n − 1) se e solo se esiste un cammino da s a t che

1In alcune formulazioni, nel problema del cammino minimo sono fissati due nodi s e t (dove t `e detto terminazioneo pozzo) e si richiede di trovare il cammino orientato di costo minimo da s a t. Tuttavia, quasi tutti gli algoritmi per questo problema calcolano contemporaneamente un cammino di costo minimo da s a qualunque terminazione v ∈ V , senza che questo richieda alcuno sforzo aggiuntivo. Per questo motivo non fissiamo la terminazione.

63

passi per tutti i nodi di D. In tal caso, ignorando l’orientamento degli archi e ripristinando lo spigolo e otteniamo un ciclo hamiltoniano in G; in caso contrario, invece, G non ha alcun ciclo hamiltoniano contenente lo spigolo e. Eseguendo dunque queste operazioni per ogni e ∈ δ(s), possiamo scoprire se G contiene un ciclo hamiltoniano. Questa procedura richiede l’applicazione dell’algoritmo A esattamente ∣δ(s)∣ volte (e quindi meno di n volte); dunque, seA `e polinomiale, ne risulta una procedura polinomiale.

Il problema del cammino minimo sembra dunque di difficile soluzione quando i costi sono arbitrari. Questo problema pu`o tuttavia essere risolto in tempo polinomiale se il grafo non contiene alcun ciclo orientato di costo negativo, cio`e se G non ha alcun ciclo orientato C tale che c(C) = ∑^e∈A(C)<0. Si noti che questa condizione `e sempre soddisfatta, ad esempio, se i costi sono tutti non-negativi (caso di evidente interesse pratico).

6.1 Cammini di lunghezza minima

Ci concentriamo prima sul caso particolare in cui ce=1 per ogni e ∈ A; in questa situazione, il costo di un cammino `e pari al numero di archi che lo compongono, cio`e alla sua lunghezza. Il problema `e dunque il seguente: dati un grafo orientato D =(V,A) ed un nodo s ∈ V , trovare, per ogni v ∈ V , un cammino di lunghezza minima da s a v (o stabilire che non c’`e alcun cammino da s a v).

Sia n =∣V ∣. Si noti che qualunque cammino in D ha lunghezza inferiore o uguale a n − 1.

Per ogni nodo v ∈ V , definiamo distanza di v da s la lunghezza di un cammino da s a v che ha il numero minimo di archi. Per k = 0, . . . , n − 1, indichiamo con V_k l’insieme dei nodi a distanza k da s. In altre parole un nodo v appartiene a Vk se e solo se il cammino minimo da sa v ha lunghezza k.² L’algoritmo proposto per la risoluzione del problema in esame si basa sulle seguenti osservazioni.

Lemma 6.1 V⁰={s}, mentre, per k = 1,... ,n − 1,

V_k={v ∈ V ∖ (V⁰∪ V1∪ . . . ∪ V_k−1) ∶ (u,v) ∈ A per qualche u ∈ Vk−1}. (6.1) Dimostrazione. `E chiaro che V0 ={s}. Fissiamo ora k ∈ {1,... ,n − 1} e definiamo Sk come l’insieme a secondo membro dell’uguaglianza (6.1). Vogliamo mostrare che V_k=S_k.

Se v ∈ V_k allora necessariamente v ∉ V0∪ ⋅ ⋅ ⋅ ∪ V_k−1. Inoltre, esiste un cammino minimo P da s a v la cui lunghezza `e k. Sia u il nodo che precede v in P . Dimostriamo che il sottocammino Psu `e un cammino di lunghezza minima da s a u. Supponiamo per assurdo che esista un cammino Q da s a u di lunghezza minore di quella di Psu. Se Q non contenesse v, allora la sequenza Q,(u,v),v formerebbe un cammino da s a v di lunghezza minore di quella di P , una contraddizione. Se, invece, Q contenesse v, allora Qsv sarebbe un cammino da s a v di lunghezza minore di quella di P , di nuovo una contraddizione. Dunque Psu `e un cammino di lunghezza minima da s a u, il che implica che u ∈ Vk−1. Questo mostra che Vk⊆S_k.

Per verificare l’inclusione inversa, osserviamo che se v ∈ S_k allora la distanza di v da s `e almeno k. D’altro canto, se v ∈ Sk allora esiste u ∈ Vk−1 tale che (u,v) ∈ A. Poich´e u ∈ V<sup>k−1</sup>, esiste un cammino P da s a u di lunghezza k − 1. Si noti che v non pu`o essere un nodo di P, altrimenti la sua distanza da s sarebbe inferiore a k. Allora la sequenza P,(u,v),v `e un

2Sarebbe pi`u corretto dire “i cammini minimi da s a v hanno lunghezza k”, visto che il cammino minimo non `e necessariamente unico (ma tutti i cammini minimi da s a v hanno ovviamente la stessa lunghezza).

6.1. CAMMINI DI LUNGHEZZA MINIMA 65 cammino da s a v di lunghezza k, quindi v ha distanza al massimo k da s. Questo implica che la distanza di v da s `e esattamente k, cio`e v ∈ V_k. Dunque S_k⊆V_k. ◻ Lemma 6.2 Sia(u,v) ∈ A, dove u ∈ V^k−1 e v ∈ Vk. Se Q `e un cammino di lunghezza minima da s a u, allora la sequenza Q,(u,v),v costituisce un cammino di lunghezza minima da s a v.

Dimostrazione. La dimostrazione `e immediata, una volta osservato che v ∉ V(Q) (altrimenti la sua distanza da s sarebbe inferiore a k, come mostrato dal cammino Qsv). ◻ L’algoritmo che proponiamo per determinare i cammini minimi dal nodo sorgente s ad ogni nodo v ∈ V costruir`a iterativamente l’insieme Vk a partire dagli insiemi V0, . . . , Vk−1: questo pu`o essere fatto grazie al Lemma 6.1. Allo stesso tempo, registreremo i predecessori di ogni nodo, cio`e per ogni nodo v ∈ V memorizzeremo un nodo u tale che u, v soddisfino le ipotesi del Lemma 6.2 (in molti casi la scelta di u non `e univoca, ma questo non crea alcuna difficolt`a). Con queste informazioni avremo la soluzione del problema: per ogni nodo v, detto k l’indice tale che v ∈ Vk, sapremo che la lunghezza di un cammino minimo da s a v `e k;

inoltre, detto u il predecessore di v memorizzato dall’algoritmo, sapremo che un cammino minimo da s a v pu`o essere costruito aggiungendo l’arco (u,v) ad un qualunque cammino minimo da s a u (Lemma 6.2); un tale cammino minimo pu`o essere determinato a sua volta verificando qual `e il predecessore del nodo u registrato dall’algoritmo e procedendo a ritroso, fino a risalire alla sorgente s.

Formalmente, l’algoritmo manterr`a, per ogni nodo v ∈ V , la distanza d(v) di v da s (dove d(v) = +∞ se tale distanza non `e ancora stata determinata) ed un puntatore p(v) ad un nodo u tale che(u,v) ∈ A e d(u) = d(v) − 1. Manterremo anche aggiornato l’insieme R dei nodi gi`a raggiunti (cio`e quelli per cui `e stata determinata la distanza da s). Diamo qui sotto la descrizione formale dell’algoritmo; si veda la Figura 6.1 per un esempio di applicazione dell’algoritmo.

Algoritmo per cammini di lunghezza minima Input: Un grafo orientato D =(V,A) ed un nodo s ∈ V .

Output: Per ogni v ∈ V , la lunghezza d(v) di un cammino di lunghezza minima da s a v ed un nodo p(v) che precede v in un tale cammino (se d(v) < +∞; altrimenti p(v) non `e definito).

1. Si ponga d(s) ∶= 0, d(v) ∶= +∞ ∀v ∈ V ∖ {s}, V⁰∶={s} e R ∶= {s};

2. Per ogni k = 1, . . . , n − 1:

2.1. Si ponga Vk∶= ∅;

2.2. Per ogni arco(u,v) tale che u ∈ V^k−1 e v ∉ R:

si ponga d(v) ∶= k, p(v) ∶= u, Vk∶= V_k∪{v} e R ∶= R ∪ {v}.

Teorema 6.3 L’algoritmo per cammini di lunghezza minima funziona correttamente ed ese-gue O(∣V ∣ + ∣A∣) operazioni.

Dimostrazione. Sia k ∈{1,... ,n − 1}. Alla fine della k-esima iterazione dell’istruzione 2, gli insiemi V0, . . . , V_k sono stati costruiti correttamente ed inoltre R = V0∪ ⋅ ⋅ ⋅ ∪ V_k: questo segue dalle istruzioni dell’algoritmo e dal Lemma 6.1. Si noti inoltre che d(v) < +∞ se e solo se v ∈ R(e in tal caso p(v) `e definito e non muter`a pi`u). Pertanto, dopo l’ultima iterazione, a ciascun nodo v ∈ R `e stato assegnato il corretto valore d(v) ed il corretto predecessore p(v). I nodi v ∉ R, invece, hanno d(v) = +∞: questi sono i nodi per i quali non esiste alcun cammino da s a v (se ci fosse un tale cammino, l’avremmo trovato prima della fine dell’algoritmo, dato che nessun cammino in D ha lunghezza maggiore di n − 1).

Per quanto riguarda la complessit`a dell’algoritmo, il passo 1 e tutte le iterazioni del pas-so 2.1 richiedono complessivamente tempo O(∣V ∣). Inoltre, ogni arco (u,v) viene analizzato al massimo una volta durante le varie iterazioni dell’istruzione 2.2 (con un numero costante di operazioni per ogni arco). Ne segue che l’algoritmo esegue O(∣V ∣ + ∣A∣) operazioni. ◻ Osserviamo che pu`o accadere di trovare R = V ben prima di raggiungere l’ultima iterazione dell’algoritmo; in tal caso si pu`o interrompere l’esecuzione, in quanto tutti i cammini minimi sono stati determinati. In modo analogo, se dopo la k-esima iterazione si dovesse avere V_k=∅, allora potremmo interrompere l’esecuzione, in quanto proseguendo troveremmo Vk+1 = ⋅ ⋅ ⋅ = V_n−1=∅.

Come visto, al termine dell’algoritmo l’insieme R conterr`a esattamente i nodi raggiungibili da s, cio`e i nodi v ∈ V per i quali esiste un cammino da s a v. Per tali nodi, inoltre, p(v)

`e definito. Sia T =(R,A<sup>′</sup>) il sottografo di D con insieme dei nodi R ed insieme degli archi A<sup>′</sup>={(p(v),v) ∶ v ∈ R ∖ {s}}. `E semplice dimostrare quanto segue.

Osservazione 6.4 T `e un’arborescenza con radice s. Per ogni v ∈ R, l’unico cammino da s a v in T `e un cammino di lunghezza minima d(v).

Dimostrazione. Per ogni v ∈ R, il grafo T contiene un cammino orientato da s a v (questo segue dalla correttezza dell’algoritmo). Per costruzione,∣A^′∣ = ∣R∣ − 1. Dunque T `e un’arborescenza con radice s. La seconda affermazione segue ancora dalla correttezza dell’algoritmo. ◻ Si dice che T `e un albero di cammini di lunghezza minima di D (si veda di nuovo la Figura 6.1, da cui si evince anche che tale albero non `e unico).