STIME E RILASSAMENTI

Problema generico di Ottimizzazione Combinatoria:

min = w_o

(di minimizzazione, senza perdere in generalità).

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

min = w_L

ovviamente si ha    w_L w_o

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 ⁿ

rilassamento Lagrangiano rispetto alle disuguaglianze (§):

z_R = min ⁿ

Proprietà principale: per ogni vettore di moltiplicatori di Lagrange l 0, z_R 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 a_ij una matrice 0-l con m righe ed n colonne. Ad ogni colonna è associato un costo c_j. 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   C_j = c_j - S_i=1..m l_ia_ij    , 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 C_j 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 x_j 1 invece di x_jI ) 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 (§):

z_S = min ⁿ

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 ⁿ

By d, y I ⁿ (§)

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

si ottiene un problema formato da una coppia di problemi

separabili:

z_D = min ⁿ

min ⁿ

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 ⁿ }

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

si fissino dei valori iniziali per i moltiplicatori l_i

si risolva LR ottenendo z_R in corrispondenza dei valori ottimi delle variabili x_j;

si calcolino i sottogradienti:

G_i = b_i - S_j=1,.,n a_ijx_j  i

si ponga ("passo"):

J p(z_U - z_R)/S_i=1,,m G_i²

l_i := max (0, l_i JG_i), i=1,,m

se test di fine non soddisfatto go to 2