Programmazione Lineare Intera
Problema (P LI):
max cx Ax ≤ b
x ≥ 0, x ∈ Zn dove Z rappresenta l’insieme degli interi.
Regione ammissibile:
Za = {x ∈ Zn : Ax ≤ b, x ≥ 0}.
Rilassamento lineare
Problema (RL):
max cx Ax ≤ b
x ≥ 0, x ∈ Rn
Regione ammissibile:
Sa = {x ∈ Rn : Ax ≤ b, x ≥ 0}.
Rilassamento lineare
Problema (RL):
max cx Ax ≤ b
x ≥ 0, x ∈ Rn
Regione ammissibile:
Sa = {x ∈ Rn : Ax ≤ b, x ≥ 0}.
Insieme convesso
Definizione Un insieme S si dice convesso se:
∀ x1, x2 ∈ S ∀ λ ∈ [0, 1] : λx1 + (1 − λ)x2 ∈ S.
Chiusura convessa
Definizione Dato un insieme T , la chiusura convessa di T , indicata con conv(T ), è il più piccolo insieme convesso contenente T .
Chiusura convessa di Za
Sia conv(Za) la chiusura convessa di Za. Si può dimostrare che, se Za 6= ∅, conv(Za) è un poliedro, cioè esiste una
matrice A′ ed un vettore b′ tale che
conv(Za) = {x ∈ Rn : A′x ≤ b′, x ≥ 0}.
Esempio
Si consideri il seguente problema (P LI), max x1 + x2
x1 + 1
2x2 ≤ 7 4 1
2x1 + x2 ≤ 7 4 x1, x2 ≥ 0 interi
Esempio
Si consideri il seguente problema (P LI), max x1 + x2
x1 + 1
2x2 ≤ 7 4 1
2x1 + x2 ≤ 7 4 x1, x2 ≥ 0 interi
Si ha Sa = {(x1, x2) : Ax ≤ b, x1, x2 ≥ 0}, con
A =
"
1 12
1
2 1
#
b =
" 7
4 7 4
# .
Esempio- continua
L’insieme Za = Sa ∩ Z2 è formato dai quattro punti (0, 0) (0, 1) (1, 0) (1, 1)
Esempio- continua
L’insieme Za = Sa ∩ Z2 è formato dai quattro punti (0, 0) (0, 1) (1, 0) (1, 1)
Si ha che
conv(Za) = {(x1, x2) : x1 ≤ 1, x2 ≤ 1, x1, x2 ≥ 0}.
Esempio- continua
L’insieme Za = Sa ∩ Z2 è formato dai quattro punti (0, 0) (0, 1) (1, 0) (1, 1)
Si ha che
conv(Za) = {(x1, x2) : x1 ≤ 1, x2 ≤ 1, x1, x2 ≥ 0}.
In tal caso
A′ =
"
1 0 0 1
#
b′ =
"
1 1
# .
Si consideri ora il problema di PL indicato con (P conv) max cx
A′x ≤ b′
x ≥ 0, x ∈ Rn Si può dimostrare che:
il problema (P LI) ammette soluzione se e solo se la ammette il problema (P conv);
Si consideri ora il problema di PL indicato con (P conv) max cx
A′x ≤ b′
x ≥ 0, x ∈ Rn Si può dimostrare che:
il problema (P LI) ammette soluzione se e solo se la ammette il problema (P conv);
ogni soluzione ottima del problema (P LI) è soluzione ottima del problema (P conv);
Si consideri ora il problema di PL indicato con (P conv) max cx
A′x ≤ b′
x ≥ 0, x ∈ Rn Si può dimostrare che:
il problema (P LI) ammette soluzione se e solo se la ammette il problema (P conv);
ogni soluzione ottima del problema (P LI) è soluzione ottima del problema (P conv);
esiste almeno una soluzione ottima (di base) del problema (P conv) che è anche soluzione ottima del problema (P LI).
Esempio-continua
Si noti che indipendentemente dalla funzione obiettivo il problema (P LI) e il problema (P conv) hanno sempre soluzione in questo caso.
Esempio-continua
Si noti che indipendentemente dalla funzione obiettivo il problema (P LI) e il problema (P conv) hanno sempre soluzione in questo caso.
Con la funzione obiettivo x1 + x2 entrambi i problemi hanno l’unica soluzione (1, 1).
Esempio-continua
Si noti che indipendentemente dalla funzione obiettivo il problema (P LI) e il problema (P conv) hanno sempre soluzione in questo caso.
Con la funzione obiettivo x1 + x2 entrambi i problemi hanno l’unica soluzione (1, 1).
Se si considera invece l’obiettivo x1, si ha che il problema (P LI) ha soluzioni (1, 0) e (1, 1), mentre il problema (P conv) ha come soluzioni l’intero segmento avente come estremi (1, 0) e (1, 1). È comunque sempre vero che esiste almeno una soluzione del problema (P conv) che è anche soluzione del problema (P LI).
Quindi ...
... se conoscessimo la matrice A′ ed il vettore b′ che
definiscono conv(Za), potremmo risolvere il problema (P LI) risolvendo il problema (P conv).
Quindi ...
... se conoscessimo la matrice A′ ed il vettore b′ che
definiscono conv(Za), potremmo risolvere il problema (P LI) risolvendo il problema (P conv).
Il problema è che in molti casi conv(Za) non è noto.
Quindi ...
... se conoscessimo la matrice A′ ed il vettore b′ che
definiscono conv(Za), potremmo risolvere il problema (P LI) risolvendo il problema (P conv).
Il problema è che in molti casi conv(Za) non è noto.
In altri casi conv(Za) è noto ma è formato da un numero esponenziale di vincoli, il che può rendere inefficiente la risoluzione del problema (P conv).
Se l’insieme di vincoli A′x ≤ b′ che definisce (P conv)
contiene un numero esponenziale di vincoli, è in alcuni casi possibile risolvere in tempo polinomiale il problema
(P conv). Più precisamente questo è possibile se e solo se è possibile risolvere in tempo polinomiale il seguente
problema (detto problema di separazione):
Se l’insieme di vincoli A′x ≤ b′ che definisce (P conv)
contiene un numero esponenziale di vincoli, è in alcuni casi possibile risolvere in tempo polinomiale il problema
(P conv). Più precisamente questo è possibile se e solo se è possibile risolvere in tempo polinomiale il seguente
problema (detto problema di separazione):
dato x ∈ Rn, è vero che A′x ≤ b′?
Se l’insieme di vincoli A′x ≤ b′ che definisce (P conv)
contiene un numero esponenziale di vincoli, è in alcuni casi possibile risolvere in tempo polinomiale il problema
(P conv). Più precisamente questo è possibile se e solo se è possibile risolvere in tempo polinomiale il seguente
problema (detto problema di separazione):
dato x ∈ Rn, è vero che A′x ≤ b′?
NB: dal momento che il numero di vincoli è esponenziale è ovviamente impossibile risolvere questo problema in tempo polinomiale verificando ad uno ad uno che tutti i vincoli
siano soddisfatti.
Una classe speciale di problemi di PLI ...
... ovvero quelli per cui
conv(Za) = conv(Sa ∩ Zn) = Sa. Equivalentemente,
(P conv) ≡ (RL) o anche A′ = A e b′ = b,
cioè il problema (P conv) coincide con il rilassamento lineare (RL) del problema (P LI).
Una classe speciale di problemi di PLI ...
... ovvero quelli per cui
conv(Za) = conv(Sa ∩ Zn) = Sa. Equivalentemente,
(P conv) ≡ (RL) o anche A′ = A e b′ = b,
cioè il problema (P conv) coincide con il rilassamento lineare (RL) del problema (P LI).
I problemi di PLI per cui si verifica questa condizione sono importanti perché sono molto più semplici da risolvere
rispetto agli altri problemi di PLI. Infatti, basta risolvere il
Continua
Essendo tutti i problemi di PL nella classe P , anche i problemi di PLI che soddisfano questa condizione appartengono alla classe P.
Continua
Essendo tutti i problemi di PL nella classe P , anche i problemi di PLI che soddisfano questa condizione appartengono alla classe P.
Inoltre, in molti casi questi problemi hanno strutture
particolari che consentono di risolverli attraverso algoritmi specifici che sono per lo più specializzazioni di metodi per risolvere problemi di PL (come il metodo del simplesso), dove la particolare struttura dei problemi consente di
implemementare in modo più efficiente i passi di tali metodi.
Matrici totalmente unimodulari
Definizione Una matrice A si dice totalmente unimodulare (TU nel seguito) se ogni sua sottomatrice quadrata ha determinante pari a 0, +1 o -1.
Matrici totalmente unimodulari
Definizione Una matrice A si dice totalmente unimodulare (TU nel seguito) se ogni sua sottomatrice quadrata ha determinante pari a 0, +1 o -1.
Si noti che una matrice TU può avere come elementi solo i valori 0, +1 e -1 visto che ogni suo elemento è una
particolare sottomatrice quadrata di ordine 1 × 1.
Proprietà
Propriet `a Se A è una matrice TU si ha che AT è TU
Proprietà
Propriet `a Se A è una matrice TU si ha che AT è TU
[A I], dove I è la matrice identica, è TU
Proprietà
Propriet `a Se A è una matrice TU si ha che AT è TU
[A I], dove I è la matrice identica, è TU
una matrice ottenuta duplicando righe e/o colonne di A è ancora TU
Proprietà
Propriet `a Se A è una matrice TU si ha che AT è TU
[A I], dove I è la matrice identica, è TU
una matrice ottenuta duplicando righe e/o colonne di A è ancora TU
una matrice ottenuta moltiplicando righe e/o colonne di A per -1 è ancora TU
Proprietà
Propriet `a Se A è una matrice TU si ha che AT è TU
[A I], dove I è la matrice identica, è TU
una matrice ottenuta duplicando righe e/o colonne di A è ancora TU
una matrice ottenuta moltiplicando righe e/o colonne di A per -1 è ancora TU
una matrice ottenuta scambiando righe di A (oppure colonne di A) tra loro è ancora TU
Proprietà
Propriet `a Se A è una matrice TU si ha che AT è TU
[A I], dove I è la matrice identica, è TU
una matrice ottenuta duplicando righe e/o colonne di A è ancora TU
una matrice ottenuta moltiplicando righe e/o colonne di A per -1 è ancora TU
una matrice ottenuta scambiando righe di A (oppure colonne di A) tra loro è ancora TU
una matrice ottenuta da A mediante un’operazione di cardine è ancora TU
Alcuni modi per riconoscerle
Esistono alcune regole per riconoscere le matrici TU, tra cui la seguente.
Osservazione Sia A una matrice i cui elementi sono tutti
uguali a 0, +1 o -1 e lungo ogni colonna non vi sono più di due elementi diversi da 0. Allora A è TU se e solo se
l’insieme delle righe di A può essere suddiviso in due
sottinsiemi Q1 e Q2 tali che se una colonna contiene due elementi diversi da 0 si ha che:
se i due elementi hanno lo stesso segno allora una delle due righe in cui si trovano è in Q1 e l’altra in Q2; se hanno segno opposto le righe corrispondenti sono entrambe contenute in Q1 od entrambe in Q2.
Esempio
A =
1 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1
Prendendo Q1 = {1, 2} e Q2 = {3, 4} si verifica
immediatamente che la condizione è soddisfatta e quindi A è TU.
Corollario
Sia A una matrice i cui elementi sono tutti uguali a 0, +1 o -1 e lungo ogni colonna non vi sono più di due elementi
diversi da 0. Se nelle colonne con due elementi diversi da 0 la somma di tali elementi è uguale a 0 (ovvero un elemento è uguale a +1 e l’altro a -1), allora A è TU.
Corollario
Sia A una matrice i cui elementi sono tutti uguali a 0, +1 o -1 e lungo ogni colonna non vi sono più di due elementi
diversi da 0. Se nelle colonne con due elementi diversi da 0 la somma di tali elementi è uguale a 0 (ovvero un elemento è uguale a +1 e l’altro a -1), allora A è TU.
Dimostrazione È sufficiente utilizzare l’osservazione precedente ponendo
Q1 = {tutte le righe di A} Q2 = ∅.
Corollario
Sia A una matrice i cui elementi sono tutti uguali a 0, +1 o -1 e lungo ogni colonna non vi sono più di due elementi
diversi da 0. Se nelle colonne con due elementi diversi da 0 la somma di tali elementi è uguale a 0 (ovvero un elemento è uguale a +1 e l’altro a -1), allora A è TU.
Dimostrazione È sufficiente utilizzare l’osservazione precedente ponendo
Q1 = {tutte le righe di A} Q2 = ∅.
Il corollario ci dice ad esempio che tutte le matrici di
incidenza nodo-arco di un grafo orientato sono matrici TU.
Esempio
Sia A la seguente matrice
A =
1 1 0 0
0 −1 1 1
−1 0 0 0
0 0 0 −1
In base al corollario tale matrice è TU.
Altro corollario
La matrice di incidenza nodo-arco per un grafo bipartito non orientato G = (V1 ∪ V2, A), dove V1 e V2 sono le due classi di bipartizione, è TU.
Altro corollario
La matrice di incidenza nodo-arco per un grafo bipartito non orientato G = (V1 ∪ V2, A), dove V1 e V2 sono le due classi di bipartizione, è TU.
Dimostrazione È sufficiente utilizzare l’osservazione precedente ponendo
Q1 = V1 Q2 = V2.
Un importante teorema
Sia
Sa(b1, b2, b3) = {x ∈ Rn : A1x ≤ b1, A2x ≥ b2, A3x = b3, x ≥ 0}
e
Za(b1, b2, b3) = Sa(b1, b2, b3) ∩ Zn,
con b1, b2, b3 vettori di interi. Si dimostra che A1, A2, A3
sono TU se e solo se per tutti i vettori di interi b1, b2, b3 per cui Sa(b1, b2, b3) 6= ∅ si ha che
conv(Za(b1, b2, b3)) = Sa(b1, b2, b3).
In particolare ...
... quello che interessa a noi è che:
A1, A2, A3 TU e b1, b2, b3 a coordinate intere ⇒ conv(Za) = Sa e quindi questo problema può essere risolto semplicemente risolvendone il rilassamento lineare.
Esempio
max x1 + x2 + x3 + x4 x1 + x2 = 2
−x1 + x3 = 4
−x2 + x4 = 3
−x3 − x4 = 2
x1, x2, x3, x4 ≥ 0 interi
Esempio- continua
Si ha
Za(b3) = {x ∈ Zn : A3x = b3, x ≥ 0}
con
Esempio- continua
Si ha
Za(b3) = {x ∈ Zn : A3x = b3, x ≥ 0}
con
A3 =
1 1 0 0
−1 0 1 0
0 −1 0 1
0 0 −1 −1
Esempio- continua
Si ha
Za(b3) = {x ∈ Zn : A3x = b3, x ≥ 0}
con
A3 =
1 1 0 0
−1 0 1 0
0 −1 0 1
0 0 −1 −1
e
b3 =
2 4 3
Esempio-continua
Poiché A3 è TU e b3 è un vettore di interi, il problema di PLI può essere risolto semplicemente risolvendone il
riassamento lineare.
