ePerTutti


Appunti, Tesina di, appunto informatica

Transmission Control Protocol

ricerca 1
ricerca 2

STIME E RILASSAMENTI


Problema generico di Ottimizzazione Combinatoria:


min = wo


(di minimizzazione, senza perdere in generalità).


Supponiamo che X Y e che sia facile risolvere il problema rilassato:


min = wL


ovviamente si ha    wL wo



Esempio:




X =


Y =


Si ha allora il rilassamento lineare che abbiamo già utilizzato applicando il metodo di Branch-and-Bound. Un altro rilassamento molto comune è il rilassamento Lagrangiano.


Si consideri il seguente problema 0-l:


z* = min n


rilassamento Lagrangiano rispetto alle disuguaglianze (§):


zR = min n


Proprietà principale: per ogni vettore di moltiplicatori di Lagrange l 0, zR z*.


Corollario: la stima migliore è data da max

(problema Lagrangiano duale)


N.B.: Affinché la funzione obbiettivo resti lineare anche per il problema rilassato bisogna rilassare vincoli lineari. Invece i restanti vincoli che definiscono la regione di ammissibilità possono essere qualunque, purché sia "facile" risolvere il problema rilassato. Se tra i vincoli rilassati ve ne sono di uguaglianza, invece che di disuguaglianza, i corrispondenti moltiplicatori di Lagrange non sono vincolati in segno.


ESEMPIO: il problema di Copertura di un Insieme (SET COVERING)


Sia aij una matrice 0-l con m righe ed n colonne. Ad ogni colonna è associato un costo cj. Si vuole scegliere un sottoinsieme di colonne di costo totale minimo che "copra" tutte le righe (ogni colonna è il vettore caratteristico di un sottoinsieme degli elementi associati alle righe).


Min , j=1,.,n


PROBLEMA RILASSATO:


Min , j=1,.,n


Sia   Cj = cj - Si=1..m liaij    , j = 1,.,n in modo da ottenere il problema rilassato nella forma


Min , j=1,.,n


Che si risolve semplicemente inserendo nella soluzione quelle colonne che corrispondono a Cj non positivi.



OSSERVAZIONI IMPORTANTI


NON è vero che una soluzione ottima del problema rilassato che risulti ammissibile sia anche ottima per il problema originale (ad esempio nel problema di Set Covering basta prendere tutti i moltiplicatori molto elevati e si mettono in soluzione tutte le colonne, che certo coprono tutte le righe, ma con costo troppo alto). Questo accade SOLO se la soluzione oltre ad essere ammissibile, è tale che l(b-Ax) = 0. Si noti che questa condizione è sempre soddisfatta se si rilassano vincoli di uguaglianza.

Se, per qualunque l, la soluzione del problema rilassato non cambia rilassando anche il vincolo di integralità (cioè richiedendo 0 xj 1 invece di xjI ) si dice che il problema rilassato possiede la proprietà di integralità

Se un rilassamento possiede la proprietà di integralità allora la stima di valore massimo ottenibile è uguale al valore fornito dal rilassamento lineare.

Se un rilassamento non possiede la proprietà di integralità, la stima di valore massimo ottenibile è maggiore od uguale al valore del rilassamento lineare.



1-ALTRI RILASSAMENTI


Invece di introdurre il termine l(b-Ax) nella funzione obbiettivo (rilassamento Lagrangiano) si può optare per lasciarlo fra i vincoli imponendo che sia 0. Si ottiene allora il cosiddetto Rilassamento Surrogato del problema (§):


zS = min n


Tale rilassamento può fornire stime migliori del rilassamento Lagrangiano, ma al prezzo, nella grande maggioranza dei casi, di un problema rilassato più difficile da risolvere.


ESERCIZIO: si verifichi quanto appena detto applicando il rilassamento surrogato al problema di SET COVERING.



SCOMPOSIZIONE LAGRANGIANA


Il problema (§) si può anche scrivere come


z* = min n

By d, y I n (§)


Se si decide di rilassare il vincolo di uguaglianza fra x ed y

si ottiene un problema formato da una coppia di problemi

separabili:


zD = min n

min n


In questo caso i moltiplicatori non sono vincolati in segno.


Qualunque sia il rilassamento scelto, è sempre necessario risolvere, almeno approssimatamene, il problema di trovare il miglior vettore di moltiplicatori possibile, detto problema Duale. Nel caso che il problema originale sia un problema di minimizzazione come abbiamo supposto (senza perdere in generalità) tale problema duale richiede di risolvere un problema di massimizzazione rispetto a l (variabili continue !) della funzione obbiettivo del problema rilassato. I principali metodi per fare questo sono: il metodo del sottogradiente, quello (euristico) di aggiustamento dei moltiplicatori, e quello di fascio. E' importante osservare che il problema (Lagrangiano o Surrogato) duale richiede di massimizzare una funzione non-differenziabile.



2-COME CALCOLARE I MOLTIPLICATORI


(a)     mediante metodi di sottogradiente

(b)     mediante aggiustamento dei moltiplicatori



METODO DEL SOTTOGRADIENTE


Si consideri il rilassamento Lagrangiano LR:


min n }


sia pI(0,2]; sia zU una stima per eccesso;

si fissino dei valori iniziali per i moltiplicatori li

si risolva LR ottenendo zR in corrispondenza dei valori ottimi delle variabili xj;

si calcolino i sottogradienti:

Gi = bi - Sj=1,.,n aijxj  i

si ponga ("passo"):

J p(zU - zR)/Si=1,,m Gi2

li := max (0, li JGi), i=1,,m

se test di fine non soddisfatto go to 2





Privacy

© ePerTutti.com : tutti i diritti riservati
:::::
Condizioni Generali - Invia - Contatta