Totale Totale Totale

Totale Totale Totale

Totale Unimodularit Unimodularit Unimodularit Unimodularità à à à

““““SapienzaSapienzaSapienza”””” UniversitSapienza UniversitUniversitUniversitààà di Roma à di Roma di Roma ---- Dipartimento di Ingegneria Informatica, Automatica e Gestionaledi Roma Dipartimento di Ingegneria Informatica, Automatica e GestionaleDipartimento di Ingegneria Informatica, Automatica e GestionaleDipartimento di Ingegneria Informatica, Automatica e Gestionale

Questa sezione Questa sezione Questa sezione

Questa sezione èèèè tratta dal materiale del prof. A. tratta dal materiale del prof. A. tratta dal materiale del prof. A. tratta dal materiale del prof. A. SassanoSassanoSassanoSassano Corso di: Ottimizzazione Combinatoria

Docente: Renato Bruni

bruni brunibruni

bruni@dis.uniroma1.it@dis.uniroma1.it@dis.uniroma1.it@dis.uniroma1.it

• Oppure che ogni verticevertice di P ha componenti 0componenti 0--11

z*=z*= min min {{cc^TTxx :: xx∈∈∈∈∈∈∈∈SS}}

Problema di PL01:

Abbiamo P = {x∈∈∈∈Rⁿ: Dx < d} formulazione di S

Sarà P = P_S = {x∈∈∈∈Rⁿ: Ax < b} = Conv(S) ??

• Oppure che argmin {c^Tx : x∈∈∈∈P }∈∈∈S∈ per ogniper ogni c∈∈∈R∈ ⁿ

• Ogni disequazione del sistema Ax < b è implicataimplicata dal sistema Dx < d; ^3x1+2x

2+ x

3−2x₄ ≤ 2

(1/2)

(1/2) 2x

1−2x₂-2x

3+2x

4 ≤ 2 Si può rispondere dimostrando che :

Si può rispondere dimostrando che :

4x1+x

2 -x

4 ≤ 3

Iniziamo da quest’ultimo caso ...

Come vedere se la Formulazione è Ottima?

Definizione 1: Una matrice A (m××××n) è detta unimodulareunimodulare se se e solo se

e solo se, per ogni sotto-matrice quadrata B (m××××m) ^di A

(base) si ha detdet(B(B))∈∈∈∈∈∈∈∈{{0,1,0,1,--11}}

Definizione 2: Una matrice A (m××××n) di è detta totalmentetotalmente unimodulare

unimodulare se e solo se, per ogni sotto-matrice quadrata di se e solo se A B (p××××p) con p>0 (=1,…,m) si ha detdet((BB))∈∈∈∈{∈∈∈∈{0,1,0,1,--11}}

1 0

1

1 1

0

0 1

1 1

1

2 3

unimodulare unimodulare

det(A)=3x1-1x2=1 ma non

totalmente totalmente unimodulare unimodulare det(B)=3,2,1,1

Non unimodulareunimodulare det(A)=1(1x1-0x1) -0(1x1-0x0)

+1(1x1-1x0)=2)

1 0

1

1 1

0

unimodulare unimodulare e totalmente totalmente unimodulare unimodulare det(B)∈{0,1,-1}

Definizioni di Unimodularità

TEOREMA 1: Sia A una matrice a componenti intere con

rank(A)rank(A)=m=m. Allora le seguenti affermazioni sono equivalenti:

1.1. AA è unimodulare;unimodulare;

2. I vertici2. vertici di PP = = {{xx∈∈∈∈∈∈∈∈RRⁿⁿ:: Ax=bAx=b , x, x≥≥≥≥≥≥≥≥00_{n n} }} sono interiinteri per ogni vettore b∈∈∈∈Z^{m (intero)}

3. Ogni sotto-matrice quadrata 3. B (m××××m) nonnon--singolaresingolare di A ha una matrice inversamatrice inversa B^-1 a componenti interea componenti intere

DIMOSTRAZIONE DIMOSTRAZIONE::

(11 ⇒ 2)2

L’equivalenza si dimostra provando che:

(22 ⇒ 3)3 (33 ⇒ 1)1

Unimodularità e Interezza

Unimodularit

Unimodularitàà e vertici interie vertici interi ((11 ⇒ 22))

AA è unimodulare unimodulare ⇒⇒⇒⇒⇒⇒⇒⇒ VerticiVertici di PP interi per interi b∈∈∈∈Z^m

DIMOSTRAZIONE

DIMOSTRAZIONE:: xx°° verticevertice di PP = = {{xx∈∈∈∈∈∈∈∈RRⁿⁿ:: Ax=bAx=b , x, x≥≥≥≥0≥≥≥≥0_{n n} }}

⇔

⇔⇔

⇔⇔

⇔

⇔

⇔ xx°° SBA SBA ((Soluzione di Base AmmissibileSoluzione di Base Ammissibile))

_n

m n

1 o

o N

B 0

0

b B

x x x

b Nx

Bx b

Ax

N

B  ≥≥≥≥









==== 











==== 

°°°°

====

++++

⇒⇒⇒

==== ⇒

−−−−

−−−−













∈

∈

∈

∈

∈

∈∈

==== ∈ _{n−−−−m}

N

m B

R x

R

x x

(((( ))))

N B

A ====

⇔

⇔⇔

⇔⇔

⇔

⇔

⇔ Esiste B sotto-matrice (m××××m) di A con det(B)≠≠≠≠0

tale che, posto: e abbiamo:

) det(B B ¹ B

−−−− ==== ++++

AA matrice matrice intera intera ((a componenti interea componenti intere)) ⇒⇒⇒⇒⇒⇒⇒⇒ BB⁺⁺ intera intera

AA matrice matrice unimodulare unimodulare ⇒⇒⇒⇒⇒⇒⇒⇒ |det|det(B)|=1(B)|=1

⇒

⇒⇒

⇒⇒

⇒⇒

⇒ BB^--11b∈b∈∈Z∈ ^m per ogniper ogni b∈∈∈Z∈ ^m ⇒⇒⇒⇒⇒⇒⇒⇒ xx°∈°∈∈Z∈ ⁿ per ogniper ogni b∈∈∈∈Z^m

matrice aggiunta

matrice aggiunta (trasposta dei compl. alg.) di BB

Vertici interi e interezza di

Vertici interi e interezza di BB^-1-1 ((2 ⇒2 33))

Vertici

Vertici di PP interiinteri per b∈∈∈∈Z^m ⇒⇒⇒⇒⇒⇒⇒⇒ ^B non-singolare ha BB^--11 interaintera

DIMOSTRAZIONE DIMOSTRAZIONE::

- Sia B una sotto-matrice (m××××m) di A con det(B)≠≠≠≠0

con

[[[[ ]]]]

m 3

2 1

B⁻⁻⁻⁻1 ==== ππππ ππππ ππππ ^L ππππ ⁽ ππππππππ_kk colonna di BB^--11 )

- Sia t un vettore interovettore intero tale che t+ππππππππ_kk ≥≥≥≥≥≥≥≥ 0_m

- Sia b(t)= Bt+uu_kk (uu_kk k-esimo vettore unitario)vettore unitario

⇒

⇒⇒

⇒⇒

⇒

⇒⇒ SBASBA del sistema Ax=b(t) , x≥≥≥≥0nn

⇒⇒⇒

⇒⇒

⇒

⇒

⇒ VerticeVertice di PP = = {{xx∈∈∈∈∈∈∈∈RRⁿⁿ:: Ax=bAx=b(t(t)) , x, x≥≥≥≥≥≥≥≥00_{n n} }} ⇒⇒⇒⇒⇒⇒⇒⇒

n m

n k m

n

k 1

m n

k 1

m n 1

0 0 t 0

u B

t 0

u Bt

B 0

t b

B  ≥≥≥≥



 



 ++++

 ====









 ++++

 ====









 ++++

 ====











−−−− −−−−

−−−−

−−−−

−−−−

−−−−

−−−− ( ) ( ) ππππ

⇒

⇒⇒

⇒⇒

⇒

⇒⇒ t+ππππππππ_kk un vettore interovettore intero ⇒⇒⇒⇒⇒⇒⇒⇒ ππππππππ_kk ^un vettore interovettore intero

[ t è un vettore interovettore intero]]

Dimostriamo che una generica colonna ππππππππ_kk ^è intera:intera

[per ipotesiper ipotesi]]

Interezza di

Interezza di BB^-1-1 e e unimodularitunimodularitàà ((3 ⇒3 11))

B non-non-singolare ha singolare ha BB^-1-1 interaintera ⇒⇒⇒⇒⇒⇒⇒⇒ AA è unimodulare unimodulare

DIMOSTRAZIONE DIMOSTRAZIONE::

- Sia B una sotto-matrice (m××××m) di A con det(B)≠≠≠≠0

⇒⇒⇒

⇒⇒

⇒

⇒

⇒ BB^-1-1 ha tutte componenti interecomponenti intere

⇒⇒⇒

⇒⇒

⇒

⇒

⇒ |det(B)| e |det(BB^-1-1)| numeri interinumeri interi

ma |det(B)| |det(BB^--11)|= |det(BBB^--11)| = 1

⇒⇒⇒

⇒⇒

⇒

⇒

⇒ |det(B)|=|det(BB^-1-1)|=1

⇒⇒⇒

⇒⇒

⇒

⇒

⇒ AA è unimodulareunimodulare

Vertici, forma Standard e forma Generale Vertici, forma Standard e forma Generale

TEOREMA 2: Il vettore xx°° è un vertice del poliedro:

PP = = {{xx∈∈∈∈R∈∈∈∈Rⁿⁿ:: AxAx ≤≤≤≤≤≤≤≤ b , x b , x ≥≥≥≥0≥≥≥≥0_{n n} }}

se e solo se

se e solo se il vettore:: è un verticevertice del poliedro

Q = Q = {{(x(x,s,s))∈∈∈∈∈∈∈∈RR^nn+m+m:: Ax+IsAx+Is = b , x = b , x ≥≥≥≥0≥≥≥≥0_{n , n ,} s s ≥≥≥≥≥≥≥≥00_{m m} }}

Dimostiamo

Dimostiamo cheche x°x° èè un vertice di un vertice di PP ⇒⇒⇒⇒⇒⇒⇒⇒ (x(x°°,s,s°°)) èè un vertice di un vertice di QQ





 





°°°°

−−−−

==== °°°°













∈

∈

∈

∈

°°°°

∈

∈

∈

∈

°°°°

Ax b

x R

s

R x

m n

-- Supponi cheSupponi che ((xx°°,s°,s°)) nonnon sia un verticesia un vertice didi QQ

((xx²²,s,s²²))

⇒⇒⇒

⇒⇒

⇒

⇒

⇒ esistono inesistono in Q Q due vettoridue vettori ((xx¹¹,s,s¹¹) ) ≠≠≠≠≠≠≠≠((xx²²,s,s²²)) tali chetali che:: (x(x¹¹,s,s¹¹))

(x(x⁰⁰,s,s⁰⁰)) (x(x°°,s,s°°)= )= αααααααα ((xx¹¹,s,s¹¹)) +(+(11--αααααααα)) (x(x²²,s,s²²) ) 1 1 >> αααααααα >00

⇒

⇒⇒

⇒⇒

⇒

⇒

⇒ xx°°= = αααααααα xx¹¹+(+(11--αααααααα)) xx²² 1 > 1 > αααααααα >00

⇒

⇒⇒

⇒⇒

⇒

⇒

⇒ xx^{1 1} = = xx^{2 2 [}xx°° è un vertice di vertice di PP]]

⇒

⇒⇒

⇒⇒

⇒

⇒

⇒ ss^{1 1} = = b-b-AAxx^{1 1} = = b-b-AxAx²² = = ss^{2 2} CONTRADDIZIONE CONTRADDIZIONE

Vertici, forma Standard e forma Generale Vertici, forma Standard e forma Generale

Dimostriamo che

Dimostriamo che ((xx°°,s°,s°)) èè un vertice di un vertice di QQ ⇒⇒⇒⇒⇒⇒⇒⇒ xx°° èè un vertice di un vertice di PP --Supponi cheSupponi che xx°° nonnon sia un verticesia un vertice didi PP

⇒⇒⇒

⇒⇒

⇒

⇒

⇒ esistono in esistono in PP due vettoridue vettori xx¹¹ ≠≠≠≠≠≠≠≠ xx²² tali chetali che:: x°x°==αααααααα xx¹¹+(+(11--αααααααα)) xx²² 1 >1 > αααααααα ^>0>0

⇒

⇒⇒

⇒⇒

⇒

⇒

⇒ ((xx°°,s,s°°))= = αααααααα (x(x¹¹,s,s¹¹)) ++((11--αααααααα)) ((xx²²,s,s²²)) 1 >1 > αααααααα ^>0>0

⇒⇒⇒

⇒⇒

⇒

⇒

⇒ ss^{1 1} = = bb--AAxx^{1 1} ≠≠≠≠≠≠≠≠ bb--AAxx²² = = ss²²

s°s° = b= b--AAxx°° = b-= b-AA((αααααααα xx¹¹+(+(11--αααααααα)) xx²²)) = =

= = αααααααα ((bb--AAxx^{1 1} ))++((1-1-αααααααα)) ((bb--AAxx²²)) == αααααααα ss¹¹+(+(11--αααααααα)) ss²²

concon (x(x¹¹,s,s¹¹)) ≠≠≠≠≠≠≠≠ ((xx²²,s,s²²)) CONTRADDIZIONECONTRADDIZIONE

Totale Unimodularit

Totale Unimodularitàà e Interezzae Interezza

TEOREMA: Sia A una matrice a componenti intere con

rank(rank(AA))=m=m. Allora I verticivertici di PP = = {{xx∈∈∈∈∈∈∈∈RRⁿⁿ:: AxAx≤≤≤≤≤≤≤≤ b , x b , x ≥≥≥≥0≥≥≥≥0_{n n} }}

sono interiinteri per ogni vettore b∈∈∈∈Z^{m (intero)} se e solo se la matrice AA è totalmente unimodulare.totalmente unimodulare.

DIMOSTRAZIONE

DIMOSTRAZIONE: : [^{Teorema 2Teorema 2}]] xx°°∈∈∈∈∈∈∈∈RRⁿⁿ è un vertice del poliedro:

PP = = {{xx∈∈∈∈∈∈∈∈RRⁿⁿ:: AxAx ≤≤≤≤≤≤≤≤ b , x b , x ≥≥≥≥0≥≥≥≥0_{n n} }}

se e solo se

se e solo se il vettore:: è un verticevertice del poliedro:

Q = Q = {{((xx,s,s))∈∈∈∈∈∈∈∈RR^n+mn+m:: Ax+Is=b , xAx+Is=b , x≥≥≥≥≥≥≥≥00_{n , n ,} ss≥≥≥≥≥≥≥≥00_{m m} }}





 





°°°°

−−−−

==== °°°°





 





∈∈

∈∈

°°°°

∈∈∈

°°°°∈

Ax b

x R

s

R x

m n

I vertici di Q Q hanno componenti intere se e solose e solo se la matrice

(A (A II_mm )) è unimodulare [unimodulare ^{Teorema 1Teorema 1}]]

DimDim UnimodularitUnimodularitàà -- Totale UnimodularitTotale Unimodularitàà 1/21/2

(A (A II_mm )) unimodulareunimodulare

⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔

[[[[

]]]]

[[[[

]]]]

Sia B una sotto-matrice (m××××m) di ((A A II_mm )) con det(B)≠≠≠≠0

[[[[

]]]]

B ==== L ⁺⁺⁺⁺ L

 

 



==== 

−−−−r m

1

I

F

0 B F

⇒

⇒

⇒

⇒⇒

⇒

⇒

⇒ |det(B)|=|det(F)|=1F

[[solo sesolo se]] A A totalmente unimodulare totalmente unimodulare ⇒⇒⇒⇒⇒⇒⇒⇒ ((A A II_mm)) unimodulare unimodulare

m 1 r

j j

M

+++

+ r 1

j j M

Dobbiamo dimostrare che:

Dobbiamo dimostrare che:

Sia F una sotto-matrice (p××××p) di A A con p>0 e det(F)≠≠≠≠0

 

 



==== 

−−−−p m 1

I F

0 B F

⇒

⇒

⇒

⇒⇒

⇒

⇒

⇒ |det(F)|=|det(B)|=1B

[se[se]] (A (A II_mm)) unimodulare unimodulare ⇒⇒⇒⇒⇒⇒⇒⇒ A A totalmente unimodularetotalmente unimodulare

{{{{

}}}}

Siano gli indici delle colonne di F

[[[[

]]]]

B ==== L ⁺⁺⁺⁺ L

Definisci la seguente base BB (m××××m) di ((A,A,II_mm ))

m 1 p

j j

M

+++

+ p 1

j j M

DimDim UnimodularitUnimodularitàà -- Totale UnimodularitTotale Unimodularitàà 2/22/2