In questo capitolo vedremo una prima metodologia di risoluzione per problemi di PLI, gli algoritmi di taglio. Prima per`o di addentrarci nella descrizione di questi facciamo un’osservazione che ci servir`a per essi e anche per i successivi algoritmi di branch-and-bound.
8.1 Trasformazione di un problema di PLI in
forma standard
Come per i problemi di PL, `e sempre possibile ricondurre un problema di PLI in forma standard. Le regole per effettuare questa trasformazione sono le stesse gi`a viste per i problemi di PL ma occorre prestare attenzione ad un ulteriore aspetto. Vediamo di illustrare questo su un semplice esempio. Si consideri il seguente problema di PLI:
max x2 x1≤ 1 2 x2≤ 1 2 x1, x2≥ 0, x1, x2∈ Z.
Se avessimo a che fare con un problema di PL potremmo trasformarlo molto semplicemente nella forma standard con l’aggiunta di due variabili y1 e y2:
max x2
x1+ y1= 1 2
x2+ y2= 12
x1, x2, y1, y2≥ 0, x1, x2∈ Z.
In questo modo ci ritroveremmo per`o con un problema in cui alcune variabili (x1 e x2) possono assumere solo valori interi e altre possono assumere anche
valori non interi (non avremmo n´e un problema di PL puro, n´e un problema di PLI puro). Infatti, ad esempio, se scelgo x1 = x2 = 0, valori ammissibili per il nostro problema di PLI, il corrispondente valore di y1 e y2`e pari a 1/2. Per ovviare a questo inconveniente e fare in modo che anche le nuove variabili possano assumere solo valori interi quando quelle originarie hanno valori interi, `e sufficiente trasformare i vincoli in modo tale che in essi compaiano solo coef-ficienti e termini noti interi. Nel nostro esempio basta moltiplicare entrambi i vincoli per 2:
max x2
2x1≤ 1 2x2≤ 1
x1, x2≥ 0, x1, x2∈ Z. e solo a questo punto aggiungere le due variabili y1e y2:
max x2
2x1+ y1= 1 2x2+ y2= 1
x1, x2, y1, y2≥ 0, x1, x2, y1, y2∈ Z.
In questo modo le variabili aggiunte y1, y2assumono sempre valori interi quan-do quelle originarie x1, x2 hanno valori interi e quindi nella forma standard possiamo imporre l’interezza anche delle variabili y1, y2. Si noti che il funzion-amento dei successivi algoritmi di risoluzione `e garantito solo se si procede alla trasformazione in forma standard nel modo sopra indicato.
8.2 Algoritmi di taglio
Per introdurre gli algoritmi di taglio dobbiamo prima introdurre il concetto di taglio valido per un problema di PLI. Sia dato un problema di PLI con il suo rilassamento lineare. Sia x∗ una soluzione ottima del rilassamento lineare, che si suppone abbia almeno una coordinata non intera (se tutte le sue coordinate fossero intere allora x∗∈ Zott).
Definizione 12 Una disequazione wx≤ v si definisce taglio valido per il prob-lema di PLI se non `e soddisfatta da x∗ ma `e soddisfatta da tutti i punti nella regione ammissibile del problema di PLI, ovvero
wx∗> v, wx≤ v ∀ x ∈ Za
Il concetto di taglio valido conduce alla definizione degli algoritmi di taglio. In essi si comincia risolvendo il rilassamento lineare del problema di PLI. Se questo ha soluzione a coordinate tutte intere, essa `e soluzione anche del problema di PLI. Altrimenti si genera (in modi che vedremo in seguito) un taglio valido, si
aggiunge questo taglio ai vincoli del rilassamento lineare e si risolve il nuovo problema di PL ottenuto con questa aggiunta. Si noti che, per la definizione di taglio valido, l’aggiunta dei diversi tagli non modifica mai la regione ammis-sibile del problema di PLI ma restringe via via quella del rilassamento lineare, tagliando via porzioni di essa che contengono le successive soluzioni ottime dei rilassamenti lineari risolti dopo l’introduzione dei tagli.
Se la soluzione ottima ha coordinate tutte intere, essa `e soluzione anche del problema di PLI. Altrimenti si genera un nuovo taglio valido che escluda la soluzione ottima del nuovo problema di PL, si aggiunge anche questo taglio ai vincoli del rilassamento lineare e si risolve il nuovo problema di PL ottenuto con questa ulteriore aggiunta. Si itera questa procedura fino a quando non si ottiene una soluzione intera (o si stabilisce che Za=∅). Notiamo che qui e nel seguito supporremo sempre che il problema di PLI e il suo rilassamento lineare non abbiano mai obiettivo illimitato. Anche se esistono tecniche per trattare tali casi, nella pratica le variabili intere hanno tipicamente dei limiti che ne im-pediscono la crescita o decrescita illimitata, escludendo quindi la possibilit`a di obiettivo illimitato. Dato il problema di PLI
max cx
aix = bi i = 1, . . . , m xj ≥ 0, xj∈ I j = 1, . . . , n formalmente, lo schema di un algoritmo di taglio `e il seguente. Inizializzazione Si risolva il rilassamento lineare
max cx
aix = bi i = 1, . . . , m xj≥ 0 j = 1, . . . , n
del problema di PLI. Se Sa=∅, allora Za =∅. Altrimenti (tralasciando il caso di obiettivo illimitato) esiste una soluzione ottima, indicata con x∗1. Si ponga k = 1.
Passo 1 Se x∗k ha coordinate tutte intere, allora si restituisca x∗k ∈ Zott. Altrimenti si vada al Passo 2.
Passo 2 Si generi un taglio valido wkx≤ vk che non sia soddisfatto da x∗k ma sia soddisfatto da tutti i punti in Za, ovvero
wkx∗k> vk, wkx≤ vk ∀ x ∈ Za.
ai tagli validi generati in precedenza e si risolva il problema di PL max cx
aix = bi i = 1, . . . , m (8.1) wrx≤ vr r = 1, . . . , k
xj ≥ 0 j = 1, . . . , n
Se tale problema ha regione ammissibile vuota possiamo concludere che Za=∅. Altrimenti sia x∗(k+1) la sua soluzione ottima.
Passo 4 Si ponga k = k + 1 e si ritorni al Passo 1.
Si noti che il problema di PL (8.1) non `e in forma standard. Tuttavia basta la semplice aggiunta di una variabile yr≥ 0 in ciascuno dei vincoli wrx≤ vr per ricondursi al formato standard. Con tale aggiunta il problema di PL (8.1) viene trasformato in quello equivalente (in forma standard):
max cx
aix = bi i = 1, . . . , m
wrx + yr= vr r = 1, . . . , k (8.2) xj≥ 0 j = 1, . . . , n
yr≥ 0 r = 1, . . . , k
Resta ancora da chiarire come si genera un taglio valido. Ci sono molti modi per generare tagli validi. Qui descriveremo un tipo di tagli detti tagli di Gomory.
8.2.1 Tagli di Gomory
Supponiamo di avere una base ottima B∗ ={xi1, . . . , xim} per il rilassamento lineare del problema di PLI. La riformulazione rispetto a tale base `e la seguente:
max γ0+Pn−mj=1 γjxim+j xi1 = β1+Pn−mj=1 α1jxim+j · · · xik= βk+Pn−mj=1 αkjxim+j · · · xim = βm+Pn−mj=1 αmjxim+j x1, . . . , xn ≥ 0
Si suppone che almeno uno dei valori βr, r = 1, . . . , m, sia non intero (se fossero tutti interi la soluzione di base associata a B∗ sarebbe non solo ottima per il rilassamento lineare ma anche per il problema di PLI). Sia βk un tale valore non intero. Scriviamo l’equazione relativa a xik:
Si consideri ora il seguente taglio, detto taglio di Gomory: −fk+ fk1xim+1+ fk2xim+2+· · · + fk,n−mxin≥ 0 dove fkj, j = 1, . . . , n− m, `e la mantissa di −αkj, cio`e
fkj =−αkj− ⌊−αkj⌋ ≥ 0
(⌊a⌋ rappresenta la parte intera di a ovvero il pi`u grande intero ≤ a), mentre fk`e la mantissa di βk, cio`e
fk= βk− ⌊βk⌋ > 0,
dove fk > 0 `e una conseguenza della non interezza di βk. Per mantenere il formato standard, possiamo aggiungere una nuova variabile y1 e riscrivere il taglio attraverso la seguente coppia di vincoli:
y1=−fk+ fk1xim+1+ fk2xim+2+· · · + fk,n−mxin (8.4) y1≥ 0.
Vogliamo dimostrare la seguente osservazione.
Osservazione 23 Il taglio di Gomory `e un taglio valido.
Dimostrazione Per prima cosa dimostriamo che la soluzione ottima del rilas-samento lineare non soddisfa questo vincolo. Notiamo che per tale soluzione ottima si ha xim+1 =· · · = xin = 0 (tutte le variabili fuori base sono nulle) e quindi, in corrispondenza della soluzione ottima del rilassamento lineare si ha:
y1=−fk< 0.
Quindi la soluzione ottima del rilassamento lineare non soddisfa, come desidera-to, il nostro taglio. Resta da far vedere che il taglio `e soddisfatto da ogni punto in Za. Prendiamo un generico punto
(xi1, . . . , xin)
in Za. Sostituiamo le coordinate di tale punto in (8.3) e (8.4) ed otteniamo rispettivamente
xik = βk+ αk1xim+1+ αk2xim+2+· · · + αk,n−mxin. (8.5) y1=−fk+ fk1xim+1+ fk2xim+2+· · · + fk,n−mxin. (8.6) Ci`o che si vuole dimostrare `e che il valore di y1 `e ≥ 0 e cio`e che la generica soluzione ammissibile in Za
xi1, . . . , xin (8.7) soddisfa il taglio. Per prima cosa dimostriamo che in corrispondenza di ogni punto (8.7) in Za si ha che il valore di y1 `e intero. Per dimostrare questo
sommiamo (8.5) e (8.6). Ricordando la definizione delle fkj e di fk, la somma ha come risultato
y1=⌊βk⌋ − xik− ⌊−αk1⌋xim+1− ⌊−αk2⌋xim+2− · · · − ⌊−αk,n−m⌋xin
Questo mostra che in corrispondenza di ogni punto in Za il valore y1 `e un valore intero (le parti intere sono tutti valori interi e le variabili xik e xim+j, j = 1, . . . , n− m in Za assumono valori interi).
Da (8.6) abbiamo anche che y1+ fk = fk1 |{z} ≥0 xim+1 | {z } ≥0 + fk2 |{z} ≥0 xim+2 | {z } ≥0 +· · · + fk,n−m | {z } ≥0 xin |{z} ≥0 .
Questo ci dice che, in corrispondenza di ogni punto (8.7) di Za, si ha che y1+ fk
`e ≥ 0 ed inoltre sappiamo che 0 < fk < 1. Infine, in precedenza abbiamo dimostrato che y1 assume valori interi in corrispondenza di ogni punto di Za. Tutto questo `e possibile soltanto se y1 ≥ 0 in corrispondenza di ogni punto di Za, come si voleva dimostrare.
La coppia di vincoli
y1=−fk+ fk1xim+1+ fk2xim+2+· · · + fk,n−mxin
y1≥ 0.
che esprime il taglio viene aggiunta alla riformulazione rispetto alla base ottima B∗ e si ottiene quindi: max γ0+Pn−mj=1 γjxim+j xi1 = β1+Pn−mj=1 α1jxim+j · · · xik= βk+Pn−mj=1 αkjxim+j (8.8) · · · xim = βm+Pn−mj=1 αmjxim+j y1=−fk+ fk1xim+1+ fk2xim+2+· · · + fk,n−mxin x1, . . . , xn, y1≥ 0
Si noti come (8.8) sia gi`a la riformulazione del nuovo problema di PL rispetto alla base B∗∪ {y1}. La soluzione di base del primale associata a questa base `e non ammissibile (la variabile y1 ha valore −fk < 0), come deve essere visto che il taglio deve rendere non ammissibile la soluzione del rilassamento lineare. Tuttavia la soluzione di base del duale associata a B∗∪ {y1} `e ammissibile (i valori γj continuano ad essere non positivi visto che non sono stati modoficati dall’introduzione del taglio). Questo ci consente di risolvere il nuovo problema di PL con il simplesso duale e con base iniziale B∗∪ {y1}. Si avr`a anche che la prima variabile ad uscire di base sar`a la y1. Perch´e?
Si noti anche come durante la dimostrazione dell’Osservazione 23 abbiamo anche dimostrato che la nuova variabile che viene introdotta (la y1) assume sempre valori interi in corrispondenza di ogni punto di Za. In pratica il risultato di interezza su y1ci consente di dire che (8.8) con l’ulteriore imposizione
x1, . . . , xn, y1∈ Z
`e una riformulazione equivalente del problema di PLI iniziale (dove per equiva-lente si intende che Zae Zottrestano invariati). Pi`u in generale, iterando quanto visto, si ha che (8.2) con l’ulteriore imposizione
x1, . . . , xn, y1, . . . , yk∈ Z
`e sempre una riformulazione equivalente del problema di PLI iniziale. Questo consente di iterare la procedura, cio`e se dopo l’aggiunta del primo taglio e la risoluzione del nuovo problema di PL (8.8) non si ha ancora una soluzione intera, possiamo generare un nuovo taglio utilizzando la stessa regola di generazione. Ma vediamo ora di chiarire meglio il funzionamento di un algoritmo di taglio che utilizza tagli di Gomory applicandolo a un problema di esempio. Si consideri il seguente problema di PLI:
max x1+ x2
2x1+ x3= 3 2x2+ x4= 3 x1, x2, x3, x4≥ 0 x1, x2, x3, x4∈ Z.
Una base otttima per il rilassamento lineare di questo problema di PLI `e la base B∗={x1, x2}. La riformulazione del rilassamento lineare rispetto a questa base `e la seguente:
max 3− 1/2x3− 1/2x4
x1= 3/2− 1/2x3 (8.9) x2= 3/2− 1/2x4
x1, x2, x3, x4≥ 0
Come si vede c’`e un termine noto non intero quindi la soluzione del rilassamento lineare:
x∗1= x∗2= 3/2 x∗3= x∗4= 0
non risolve il problema di PLI. A questo punto aggiungo un taglio di Gomory. Considero l’equazione
x1= 3/2− 1/2x3
e da questa, in base alle regole viste, si ricava il seguente taglio: −1/2 + 1/2x3≥ 0.
Aggiungendo una variabile y1 il taglio viene espresso dalla seguente coppia di vincoli:
y1=−1/2 + 1/2x3, y1≥ 0.
Aggiungiamo ora questi alla riformulazione (8.9) rispetto alla base ottima B∗. max 3− 1/2x3− 1/2x4
x1= 3/2− 1/2x3
x2= 3/2− 1/2x4
y1=−1/2 + 1/2x3
x1, x2, x3, x4, y1≥ 0
Possiamo notare che questa `e gi`a la riformulazione del nuovo problema rispetto alla base B∗∪ {y1} = {x1, x2, y1}. La soluzione di base del primale associata a questa base `e non ammissibile (il valore di y1`e−1/2) ma la soluzione di base del duale associata alla stessa base `e ammissibile (i coefficienti delle variabili fuori base nell’obiettivo non sono stati modificati e continuano ad essere negativi). Quindi possiamo applicare il simplesso duale con base iniziale {x1, x2, y1}. Si verifica immediatamente che non sono soddisfatte n´e la condizione di ottimalit`a, n´e la condizione di illimitatezza dell’obiettivo duale. Chiaramente, la prima variabile che dovr`a entrare in base sar`a l’unica con un valore negativo e quindi dovr`a essere la y1. In base alle regole viste, l’unica variabile che potr`a entrare in base `e la x3. Passeremo quindi alla base{x1, x2, x3} rispetto alla quale avremo la seguente riformulazione: max 5/2− y1− 1/2x4 x1= 1− y1 x2= 3/2− 1/2x4 (8.10) x3= 1 + 2y1 x1, x2, x3, x4, y1≥ 0
La base `e ottima per il nuovo problema di PL ma purtroppo abbiamo ancora un termine noto non intero e quindi non abbiamo ancora una soluzione ottima del problema di PLI. Allora, dobbiamo aggiungere un ulteriore taglio di Gomory. La regola di generazione `e la solita. Per prima cosa selezioniamo un’equazione con termine noto non intero. Qui la sola possibile `e:
x2= 3/2− 1/2x4.
Da questa si genera, in base alle regole viste, il seguente taglio: −1/2 + 1/2x4≥ 0.
Aggiungendo una nuova variabile y2il taglio viene espresso dalla seguente coppia di vincoli:
Aggiungiamo ora questi alla riformulazione (8.10) rispetto alla base ottima {x1, x2, x3}. max 5/2− y1− 1/2x4 x1= 1− y1 x2= 3/2− 1/2x4 x3= 1 + 2y1 y2=−1/2 + 1/2x4 x1, x2, x3, x4, y1, y2≥ 0
Possiamo notare che questa `e gi`a la riformulazione del nuovo problema rispetto alla base {x1, x2, x3, y2}. La soluzione di base del primale associata a questa base `e non ammissibile (il valore di y2`e−1/2) ma la soluzione di base del duale associata alla stessa base `e ammissibile (i coefficienti delle variabili fuori base nell’obiettivo non sono stati modificati e continuano ad essere negativi). Quindi possiamo applicare il simplesso duale con base iniziale{x1, x2, x3, y2}. Si verifica immediatamente che non sono soddisfatte n´e la condizione di ottimalit`a, n´e la condizione di illimitatezza dell’obiettivo duale. Chiaramente, la prima variabile che dovr`a entrare in base sar`a l’unica con un valore negativo e quindi dovr`a essere la y2. In base alle regole viste, l’unica variabile che potr`a entrare in base `e la x4. Passeremo quindi alla base {x1, x2, x3, x4} rispetto alla quale avremo la seguente riformulazione: max 2− y1− y2 x1= 1− y1 x2= 1− y2 x3= 1 + 2y1 x4= 1 + 2y2 x1, x2, x3, x4, y1, y2≥ 0
La base `e ottima per il nuovo problema di PL e tutte le variabili hanno valore intero. Abbiamo quindi la seguente soluzione ottima del problema di PLI:
x∗1= x∗2 = x∗3= x∗4= 1.
Ci si pu`o chiedere se siamo stati solo fortunati oppure con i tagli di Gomory l’algoritmo di taglio termina sempre in un numero finito di iterazioni. Vale la seguente osservazione.
Osservazione 24 Se ad ogni iterazione il taglio di Gomory viene realizzato a partire dalla prima equazione con un termine noto βk non intero, allora l’algoritmo termina in un numero finito di iterazioni.