Risposte alle domande di esame Ottimizzazione Combinatoria 2 - Sassano

Sistemi di indipendenza

 Definire un sistema di indipendenza ⊆

Dato un insieme base Γ=[1,2,…n} di elementi e l’insieme delle soluzioni ammissibili S={F1,F2…Fm} con Fi

,

S è un sistema di indipendenza se e solo se ogni volta che un insieme T qualsiasi tale che T⊆ allora T∈

, ovvero vale la proprietà dell’ereditarietà (se un insieme appartiene alla famiglia allora appartengono alla

famiglia anche tutti i suoi sottoinsiemi).

 Definire basi e circuiti del sistema di indipendenza ( ) ( )

∈ ∩ ⊃ ∉

Un insieme B è una base di S se è un indipendente massimale: (B non può

essere contenuto in nessun altro insieme di S). Un insieme C è un circuito se non appartiene alla famiglia

( ) (

∉ ∩ ⊂

ma tutti i suoi sottoinsiemi sì (C è un dipendente minimale): C circuito se e solo se

)

∈ .

 Definire rango, lower rank e proprietà del rango

}.

r(X) con X⊆ è definito così: r(X)=max{|T|: T⊆X, T∈ Proprietà:

1. r(Ø)=0

2. r(X)≤r(Y) se X⊆ (rango non decrescente)

3. r(X)=|X| se e solo se X∈ (altrimenti è <)

∀e∈ è

4. r(X)=|X|-1∩r(X-{e})=|X|-1 (solo la prima non basta perché non

è detto che sia un circuito anche se è vera la condizione, solo la seconda non basta perché non

esclude che il rango di X possa essere pari alla cardinalità)

, , ∀e∈ \}.

lr(X) con X⊆ è definito così: lr(X)=min{|T|: T⊆ T∈ T∪{e}∉ È la minima cardinalità di un

insieme T contenuto in X ed appartenente ad S tale che se gli viene aggiunto qualunque altro elemento di X

∀ ⊆

non appartiene più ad S. è il minimo indipendente massimale in X. In generale lr(X)≤r(X)

 Definisci matroide ∀X⊆ .

Un sistema di indipendenza S è una matroide se e solo se lr(X)=r(X) (in una matroide tutte le basi

hanno la stessa cardinalità)

 Descrivi l’algoritmo Greedy

max{( ): è }

Dato un problema l’algoritmo esegue i seguenti passi:

2 … ≥

1. Ordina gli elementi per pesi decrescenti {e1,e2….en}: c1≥

2. Inizializza T :=0

0

3. For i:=1 to n

∪{ei}ϵS ∪{ei}

4. Do if T then Ti:=T

i-1 i-1

5. Else Ti:=T

i-1

Tn soluzione Greedy, base di S. soluzione euristica c(Tn)<=c(F*). Al massimo n passi

 Dimostrare teorema di Jenkyns Korte Hausman

Date Tn ed F* soluzioni greedy e soluzione ottima del problema di massimo insieme indipendente max c(F),

min()() ()

()

= ≤ ≤ 1

allora DIM: poniamo Γi={e1…ei} e Fi=F* i=1…n dove Fi è l’insieme che

() (∗)

l’algoritmo greedy ha costruito al passo i. poiché FiϵS |Fi|≤r(Γi). Inoltre per costruzione greedy Ti⊆Γi e ogni

{}

∪ ∉

elemento eϵΓi\Ti ha la proprietà che quindi Ti massimale in Γi, allora |Ti|≥lr(Γi). Osserviamo

∑ ()

0, =

che l’elemento ekϵTn se e solo se Tk/Tk-1≠ dunque |Tk|-|Tk-1|=1, quindi c(Tn)= ∈

=1

∑ (|| | 1|)()

− − vengono sommati solo gli elementi per cui la differenza è 1. Analogamente

=1

|| | 1| ( ∗) ∑ () ∑ (||

∈ ∗ − 1 ≠ 0 − − = 1 = = −

quindi ∈∗

=1

| 1|)() () ∑ (|| | 1|)()( ) ()||

− = − − = +

ora:

−1 −1

∑ ( 1))|| ()() ∑ () ( 1)() ()[ ()()

(() − + ≥ + ( − + ≥ +

=1 =1

−1 −1

∑ ( 1))()] ()[ ()|| ∑ ( 1))||]

(() (()

− + ≥ + − + con passaggi

=1 =1

=1

∑ (|| | 1|)()

= () − −

analoghi ai precedenti otteniamo . Poiché ek∈F* se e solo se Fk/Fk-1≠

=1

∑ (|| | 1|) () ()(

0 − − ∗)

quindi see solo se |Fk|-|Fk-1|=1 abbiamo c(F*)= dunque c(Tn)≥

1

 Dimostra teorema di Rado Edmonds

Un sistema di indipendenza S è una matroide se e solo se per ogni possibile funzione obiettivo c a

coefficienti positivi l’algoritmo Greedy trova una soluzione ottima del problema di massimo indipendente

max c(F) DIM: se S è matroide per ogni X⊆Γ: lr(X)=r(X), allora per il teorema di Hausman c(Tn)/c(F*)

(FϵS)

compreso tra 1 e 1 quindi Tn soluzione ottima. Se S non è matroide esiste una funzione obiettivo c per cui

()

Tn non è ottima cioè c(Tn)<c(F*). Se S non è matroide deve esistere una X per cui lr(X)≤ quindi

esistono due indipendenti massimali B1 B2 contenuti in X con |B1|=lr(X)<r(X)=|B2|. Costruiamo c per cui

1

Tn=B1 ma F*≠ quindi B1 non è soluzione ottima. Assegniamo a tutti gli elementi che appartengono a B1

peso c(ei)=1+δ (0<δ<(|B2|-|B1|)/|B1|) e a tutti gli elementi di B2 ma non di B1 c(ei)=1, tutti gli altri 0. Se

applichiamo Greedy inserisce in Tn tutti gli elementi di B1, poiché B1 è massimale in X ogni elemento di

|1|(|2|−|1|)

() (1) |1| |1| |1| |1| |2|

∉ = = + < + = + −

Tn\B1 X e ha peso 0, quindi: |1|

|1| |2| |2| |1 2| (2)

= ≤ + ∩ = allora Tn non otttima

 Dimostra che Pr è una formulazione

{( ):

max è }

Sia il massimo insieme indipendente, problema di OC con funzione

{:

= ∈ }. ∈ ⟺

obiettivo lineare. Sia Il teorema I1 afferma che

|⋂| () (⋂ )

≤ ∀ ⊆ Γ. ∈ → ∈ ∀ ⊆ Γ ⋂

DIM I1: Se allora è un sotto insieme di F, F è

|⋂| (⋂) ()

→ = ≤ ∀ ⊆ Γ

un indipendente dunque vale la proprietà di ereditarietà. Il rango è

|⋂|

⋂ ∉ → ∃ ⊆ Γ: >

non decrescente, il rango di è al più uguale al rango di X. Viceversa, se

| | ( ). |⋂| | | ( ) ()

() ∉ , > = = > =

Infatti, se F è un dipendente, Ma per Allora

|⋂| ( ). |⋂| () |⋂|

∃ ⊆ Γ: > ∈ ⟺ ≤ ∀ ⊆ Γ,

Abbiamo quindi dimostrato che dove è il

|⋂| ( ) ( ) ∑ ∑

= = =

prodotto interno dei vettori di incidenza di F e di A . Allora

∈Γ ∈A

∑ () {0,1}n.

∈ ⟺ ≤ ∀ ⊆ Γ se e solo se x ∈ Possiamo dunque definire la formulazione

∈A

∑ ()

≤ ∀ ⊆ Γ

∈A

{

= ⟹ max

rango: La formulazione rango è un rilassamento della

≥ 0 ∈Γ |Γ|

∈ ∩{0,1}

formulazione ottima, dunque ancora una formulazione ma con meno vincoli.

 Dimostrare che la formulazione rango Pr è ottima se il sistema di indipendenza è una matroide

∑ ()

∑

max ⊆

∑

{ {

∑ () ≥ ∀ ∈

La coppia primale duale della PR è: ≤ ∀ ⊆ ∋

∈ ≥ 0 ∀ ⊆

≥ 0 ∀ ∈ min rTy

max cTx DTy ≥ c

{

Dx ≤ r

il primale può essere riscritto nella forma{ ed il duale y ≥ 0(2n)

x ≥ 0n

poniamo gli elementi in ordine decrescente di peso ci e ricordiamo che i c <0 li possiamo eliminare senza

i

modificare il valore delle soluzioni ottime primale e duale. Poniamo Ai={e1…ei} per i=1..n, il vettore y così

= − + 1, 1 ≤ ≤ − 1

= , =

{ ≥o

definito: è ammissibile per il problema duale infatti c per iϵ{1…n} e

i

= 0, ≠ ∀ = 1. . −1

∑ ∑ ∑ ( 1)

≥ 0 ∀ ⊆ = = + − + =

c >=c +1 per iϵ{1,…n-1} dunque y inoltre:

i i A :∈ ≥ =

(vale perchè siamo in presenza di una sommatoria telescopica) allora y è soluzione ammissibile. Sia ora

∩

T la soluzione Greedy e T =A e sia x̅ il vettore di incidenza di T , abbiamo che:

n i i n

( ) ( 1)

= 1 ⇒ − − = 1 ( ) ( 1)

{ ⇒

= − − infatti siccome S è matroide abbiamo

( ) ( 1)

= 0 ⇒ − − = 0

lr(Ai)=r(Ai) quindi lr(Ai)=|Ti|=r(Ai) ora se e ϵTn (x̅

i=1) abbiamo Ti=Ti-1U{ei} quindi r(A )-r(A )=1. Se invece

i i i-1

∑ ∑

=

=

ei∉ (x̅

i=0) Ti=T quindi r(Ai)-r(A )=0. Il valore della soluzione greedy quindi è:

i-1 i-1 ∈ ∈

=1 −1

∑ (( ) ( 1)) ∑ (( ) ( 1)) () ∑ ( )( ( 1))

− − = − − = n ∗ + − + =

∈ =1

−1

() ∑ ( ) ∑ ( )

+ = uguale al valore della soluzione duale y quindi per ogni cϵRn il

⊆

=1

vettore x̅ della corrispondente soluzione greedy è ottimo per il problema primale, quindi PR=PS (la form

rango ottima). 2

 Dimostrare che la formulazione circuiti Pc è una formulazione

∑ | | ∑ ()

≤ − 1 è ≤ ∀ ⊆ Γ

∈C ∈A

{ {

= ⊃ =

Data la formulazione , Il

≥ 0 ∈Γ ≥ 0 ∈Γ

∈ ⟺ ∈ ∈ ⟹ ∈ ⟹ ∈

teorema I2 afferma che è una formulazione: . DIM: Se

∑

⊃ ∉ , ⊆ = 1 ∀ ∈ ⟹ =

poiché . Se viceversa esiste un circuito ma allora

∈C

| | ⟹ ∉ . La formulazione circuiti è un rilassamento della formulazione ottima, dunque ancora una

formulazione ma con meno vincoli.

 Definire sistema di indipendenza per gli stabili

S è l’insieme degli insiemi stabili di un grafo G(V,E) ovvero è composto da insiemi di nodi a coppie non

adiacenti. Gli elementi sono i nodi.

 Definire basi e circuiti per gli stabili

Una base è uno stabile massimale. Un circuito è una coppia di nodi collegati da un arco ovvero tale che

v v ϵE

i h  Formulazione circuiti per gli insiemi stabili

+ ≤ 1 ∈

Pc={ ≥ 0 ∈

 Definire il sistema di indipendenza di un knapsack a coefficienti positivi

S è l’insieme di progetti compatibili con un budget, cioè soluzioni di knapsack a coefficienti positivi.

 Definire basi e circuiti del knapsack

Circuito: insieme di progetti non compatibile con un budget ma tale che ogni suo sottoinsieme è

compatibile

Base: insieme di progetti compatibile massimale

 Definire il matching di un grafo

S={matching di un grafo G(V,E)} cioè insiemi degli archi non incidenti nello stesso nodo

 Definire basi e circuiti del matching

Circuiti: {ei,eh} con ei, eh incidenti nello stesso nodo. Basi: matching massimali

 Formulazione circuiti matching

(),

+ ≤ 1 , ∈ ∈

Pc={ ottima se e solo se il grafo è bipartito

≥ 0 ∈

 Definire sistema di indipendenza di vettori linearmente indipendenti

∑

↔ = 0 = 0

S={insiemi di vettori LI}, Γ={v1,…v