Appunti del corso di Ottimizzazione Combinatoria 2 prof Antonio Sassano

CAMMINO MINIMO COL VINCOLO DI BUDGET dove

abbiamo una funzione lagrangiana per ogni cammino

minimo, abbiamo il costo del cammino, la penalizzazione,

non avremo un esercizio così all’esame ma aiuterebbe a

capire come è fatto un passo del metodo del subgradiente

in quel caso.

In questo esempio abbiamo calcolato L1...L4, tutti quanti

rappresentabili. Abbiamo 4 rette, (b-Axk) è la pendenza,

wTxk costante se k è fissato.

La funzione in rosso indica il minimo per ogni u dei valori

assunti sulle 4 rette.

Per u che va da 1/2 a 2/3 abbiamo il valore minimo che vale 2.

Lo scalare u all’inizio lo mettiamo a 0.

Devo calcolare L(0), cioè il minimo che lo ottengo sulla retta L4. La retta su cui trovo il minimo definisce kbarrato.

Devo confrontare -3 con -infinito, quindi mi segno Lbest e ubest perché ho trovato una soluzione migliore della

precedente.

Come trovo un possibile subgradiente: ricordo il teorema che dice che il subdifferenziale in u0 corrisponde a b-

Axkbarrato. Questo è un possibile subgradiente. Prendo allora una retta che passa per il punto 0, L0, questa è proprio

la retta su cui ho trovato il minimo. La pendenza della retta 4 vale 2, quindi il subgradiente vale 2.

Scelgo un subgradiente, ce ne è uno solo quindi scelgo s=2.

Ricordiamoci che quello che aggiorniamo è u, ci muoviamo solo sull’asse delle ascisse, quindi solo avanti e indietro,

non ci muoviamo in alto o in basso. La direzione di s è avanti o indietro sull’asse delle ascisse.

Facciamo quindi crescere u (abbiamo s>0, quindi cresce).

Il nuovo punto sarà 2, mi sposto nel punto 2 dal punto 0 dove mi trovavo prima. Divido per 2 il θ che ora vale 1/2.

-6 è più piccolo di -3 quindi non aggiorno, il lower bound

calcolato qui non è migliore di quello trovato al passo

precedente.

Un solo subgradiente (una sola retta per quel punto) il

subdifferenziale contiene solo -3, c’è una pendenza

negativa, retta decrescente al crescere di u.

In pratica lo spostamento a destra o sinistra dei valori di u

hanno lo stesso valore della penalità, si sceglie la

penalizzazione giusta da dare al vincolo che ha rilassato,

se sale allora si penalizza di più, se scende allora si

penalizza di meno.

10

Ora troviamo come valore -2 quindi aggiorniamo il valore

perché è un lower bound migliore.

Per quel punto passano 2 rette allora ho due possibili

subgradienti.

Ho due pendenze la pendenza 2 e la pendenza 0, posso

scegliere una delle due, teoricamente potrei scegliere una

qualsiasi retta del cono tra le due rette, ma scegliamo una

delle due rette liberamente.

Se avessimo scelto 0 al passo 2 il punto θ2 per 0 faceva 0

quindi sarei stato nello stesso punto, avrei ricalcolato il

valore con un passo più piccolo quindi sarei rimasto nello

stesso punto.

Se troviamo 0 in qualche subgradiente ci fermiamo perché

vuol dire che abbiamo finito.

Mi fermo sia perché 0 appartiene al subgradiente, sia

perché ho costruito un θ che è minore o uguale ad ε.

La soluzione ottima è 1/2

11

Cammino minimo vincolato: applicazioni,

algoritmi, teoria

Esempio MIT L’esempio è il cammino minimo vincolato.

Voglio trovare il cammino minimo tra due nodi, voglio però il

minimo costo perché ho un vincolo di budget.

Trova il cammino minimo da 1 a 6 col minimo costo, col tempo

massimo 14

In rosso tempi di transito, in nero costi

Ci sono due parametri, cammino minimo con budget. Se

prendessi il cammino di costo minimo arriverebbe in ritardo per

via del budget di tempo, quindi non va bene.

Trovare il cammino che costa di meno ma che rispetti il budget

è un problema difficile.

Vogliamo risolvere il problema.

Il rilassamento lagrangiano interviene quando vedo un problema

facile che è complicato da alcuni vincoli complicanti

Il problema del cammino minimo è facile, è complicato dal fatto

che devo metterci meno di 14 ore.

Data una rete e dato un costo per l’arco ij (numeretti neri), w( P)

è il costo del cammino P (somma dei costi/pesi dei singoli

elementi, vale il principio di sovrapposizione degli effetti), tij è il

tempo che ci metto per andare da un nodo all’altro. T è un

upper bound, è un budget del tempo di transito, la somma dei

tempi di transito dovrebbe essere più piccola di T. t( P) è il

tempo complessivo come somma dei tempi, anche qui vale il

principio di sovrapposizione degli effetti.

P è l’insieme dei cammini dal nodo 1 al nodo n.

Voglio il costo minimo subjet to (con il vincolo) che t( P) sia minore del budget. Voglio sceglie il cammino minimo, ho

un vincolo di knapsack di budget.

Abbiamo penalizzato la funzione obiettivo, nel caso in cui viene violato il vincolo. Ora la funzione obiettivo è più

complicata.

Avevamo un problema di cammino minimo, abbiamo rilassato il problema, dobbiamo trovare il cammino minimo con

una funzione obiettivo più complicata. Questo è il modo americano di scrivere, noi dobbiamo usare il

suo, slide seguente

Per ogni fissato u fai questo calcolo

È un problema di cammino minimo, ma la funzione obiettivo

è modificata dalla presenza di u

Il vettore di incidenza è un vettore in cui cij è 1 se ij appartiene a

P.

Faccio quindi le somme di tempi e costi dei soli archi che

appartengono a P, infatti tutti i pesi sono moltiplicati per il

vettore di incidenza.

Minimizza una funzione obiettivo lineare

Qst è il poliedro, insieme di equazioni che rappresentano i cammini minimi, dovrà dire che in ogni nodo il numero di

archi entranti è uguale al numero di archi uscenti, il flusso che entra in un nodo deve uscire da quel nodo ecc

Potrei fissare u a 0, in quel caso i pesi sono wij e dimentico i

tempi di transito, quindi me ne frego di arrivare in orario.

Se invece voglio considerare tanto i tempi metto u molto grande

L’alternativa è sceglie u numero qualunque

Quando scelgo u=2,1 cambiano tutti i pesi, quindi trovo il

cammino minimo che deriva dall’aver messo un vincolo nella

funzione obiettivo.

Abbiamo fissato nella funzione lagrangiana il valore xk che in

questo caso significa fissare il cammino.

Il coefficiente è positivo tutte le volte che arrivo in ritardo, infatti

indica il costo dell’arrivare in ritardo, dipende ovviamente da u.

Ogni soluzione xk (cammino P) definisce un iperpiano (retta)

Prendo il cammino disegnato in verde e sommo tutti i valori

10+5+10+2, che fa 27, allora w=27. 3+7+1+2 ci metto 13,

questo è il tempo di transito, potevo metterci massimo 14,

quindi questo cammino costa molto (27) ma arrivo in orario. La

retta avrà pendenza negativa.

Il cammino verde rispetta il vincolo di orario.

Cammino in rosso: il suo costo vale 10+5+1=16. Il tempo di transito vale 3+7+7=17. Quindi questo è un cammino che

mi fa arrivare in ritardo, il coefficiente della u è positivo. La pendenza della retta è positiva.

Tutte le rette che hanno pendenza positiva al crescere delle u corrispondono a cammini per cui arrivo in ritardo, tutte

quelle con pendenza negativa mi fanno arrivare in orario.

Quindi anche soluzioni che non erano ammissibili precedentemente ora le devo considerare.

1-2-4-6 viola il vincolo

La funzione lagrangiana è l’inviluppo, l’iperpiano è dato dalle

rette più basse, abbiamo quindi un numero basso di iperpiani di

supporto, tantissimi sopra

P è l’insieme di cammino a 1 a 6

B contenuto in P (insieme di tutti i possibili cammini), B è un

sottoinsieme di cammini

Path(u) è l’iperpiano di supporto che corrisponde alla soluzione

ottima.

Sia u(B) il valore di u che ottimizza Lb(u) (ottimo che trovo

quando ho buttato via una serie di iperpiani e mi sono tenuto

solo quelli che stanno in u(B).

M è grande

Calcola il cammino corrispondente ad una u=0 e quello che

corrisponde ad un grande M, cioè calcola il cammino di quello

che vuole spendere il meno possibile e quello che vuole arrivare

il prima possibile.

Risolve il problema di ottimizzazione con un sottoinsieme B dei

cammini

Trova la soluzione ottima fissato B, rimetti poi a posto tutti gli iperpiani e calcola L(u), questo è facile, si domanda se è

uguale alla soluzione trovata allora quella è la soluzione ottima, se non lo è allora aggiungi il cammino ottimo di u(B)

all’insieme B e risolvi di nuovo. Noi ora facciamo 4 passi, all’esame ne chiederà uno solo

Sceglie due cammini che corrispondono a rette, uno con

pendenza positiva l’altro con pendenza negativa, uno a costo

minimo che si disinteressa del tempo di arrivo e guarda solo i

costi, poi prende un altro cammino che lo fa arrivare al tempo 8

ma che costa 24 (pendenza negativa di 6).

Ora il problema è con B, ho preso una B molto piccola fatta da

due soluzioni, (ovviamente se abbiamo trovato la soluzione che

spende il meno possibile e arriva in tempo allora quella è la

soluzione ottima, meglio di così non possiamo fare). Dobbiamo

trovare un punto nelle ascisse che consenta di salire il più

possibile, trovare quindi il massimo dell’inviluppo inferiore.

Si risolve col metodo del simplesso, all’esame ci verrà fornita la soluzione per non applicare il simplesso.

Trovo quindi le due coordinate nella soluzione ottima che indicano il punto in cui vedo il soffitto più lontano e a che

altezza sta.

Lui ci darà i numeri 2,1 e 11,4. A questo punto so qual è il punto in cui calcolare la funzione originaria,

concettualmente dovrei rimettere a posto tutti i vincoli e ottimizzare.

Il costo modificato (somma dei costi degli archi) è 36, il costo di

questo cammino nel grafo originario è 15, il tempo di transito nel

grafo originario è 10.

L(u(B)) non dobbiamo fare tutti i calcoli, ce li sta solo facendo

vedere. Per fissato u sappiamo trovare il valore ottimo della

funzione obiettivo, in rosso è il valore della funzione obiettivo

calcolata su questo cammino. L(u(B)) è 6,6, dobbiamo sempre

sottrarre la costante con questo modo. Abbiamo anche un altro

metodo, il risultato finale è sempre 6,6

Dobbiamo confrontare il valore ottenuto con 11,4. Questo

numero è l’altezza, il valore dell’ordinata del punto ottimo

trovato prima v(B).

Abbiamo trovato 6,6 perché c’è un iperpiano che ci ha impedito di salire.

La soluzione non è ottima per il problema originario, devo aggiungere un iperpiano.

Ora aggiungo un iperpiano che prima non c’era. Ora ho 3

iperpiani, sono tutti e 3 di supporto.

Il coefficiente è sempre la differenza tra il tempo di transito ed il