Appunti Ottimizzazione Combinatoria II

∈S

Dimostrazione:

⇒ ∀ ⊆ Γ

: se S è una matroide allora si ha che lr(X)=r(X) . Allora per il teorema di Jenkyns-Korte-

Hausman si ha: ∗

)/( )

(S) = ()/() = 1 ≤ ( ≤ 1

⊆Γ

∗

)/( )

( = 1

Quindi e quindi è la soluzione ottima.

⇐: vogliamo dimostrare che se Greedy produce per ogni funzione obiettivo c a coefficienti positivi,

∗

) )

( = (

una soluzione con allora S è una matroide. Equivalente a dimostrare che se S

non è matroide allora esiste una funzione obiettivo c a coefficienti positivi per la quale la soluzione

∗

) )).

( < (

Greedy non è la soluzione ottima (

∈ Γ

Se S non è matroide allora esiste un tale che lr(X)<r(X) quindi esistono due insiemi

| | | |

= () < () =

indipendenti massimali (basi) contenute in X e tali che .

1 2 1 2

) )

( = (

Quindi se S non è matroide esiste una funzione obiettivo c “sfortunata” per la quale 1

∗

) ).

( < (

cioè è la soluzione Greedy ma non è la soluzione ottima, infatti Costruiamo

1 1

Γ:

quindi i pesi c per ogni elemento contenuto in

• ) | | |]/| |

( = 1 + δ ∈ 0 < δ < [| −

: per gli elementi

1 2 1 1

• )

( = 1 ∈ \

: per gli elementi

2 1

• )

( = 0 Γ ℎ è è

: per tutti gli altri elementi di

1 2

Quindi Greedy sceglierà tutti gli elementi di in quanto sono quelli con peso maggiore e non

1

potrà aggiungere altri elementi di X perché è massimale in X. Greedy potrà aggiungere solo

1

elementi che non sono in X ma questi hanno peso 0 per come abbiamo costruito i pesi.

:

Quindi la soluzione Greedy sarà formata solo dai pesi degli elementi di 1

| |(| |−| |)

1 2 1

)= ) | | | | | | | | | | | | | | | |

( + < + = + − = ≤ +

c( =

1 1 1 1 1 2 1 2 2

| |

1

|

| ∩ = ( )

1 2 2 | | |]/| |

0 < δ < [| −

Dove abbiamo sfruttato il fatto che .

2 1 1

)= ) ).

( < (

Quindi non è soluzione ottima perché c( potrebbe essere una

1 2 2

∗

)= ) ) ).

( < ( ≤ (

soluzione ottima in quanto: c( Sicuramente non sarà ottima

1 2 1

∗

) ).

< (

perché : c(

1

Esempi di matroidi

• Matroide generica : es. S={0, {1}, {2}, {3}, {1,2}, {2,3}} le basi hanno tutte la stessa

cardinalità pari a 2;

• ||

⊆ Γ: ≤ }

Matroide uniforme: (k intero) S= {F ;

• ∈ Γ ={1, ∈

Matroide Lineare : A matrice (mxn), colonna di A con 2, …, n}, S= {

Γ: { : ∈ } lineramente indipendente;

• Matroide Grafica o Forest Matroid: Γ = ; ⊆ Γ: }.

è dato un grafo qualsiasi G(V,E) con S={ Vogliamo dimostrare

che il sistema di indipendenza delle foreste è una matroide grafica. Procediamo prendendo

un insieme generico e facciamo una dimostrazione generica per poi estendere il

ragionamento.

Teorema: il sistema di indipendenza delle foreste di un grafo G(V,E) è una matroide grafica.

Dimostrazione: ∀ ⊆ Γ,

Vogliamo dimostrare che lr(X)=r(X) cioè che S sia una matroide.

Sia X un qualsiasi sottoinsieme degli archi del grafo G(V,E) e sia H(V,X) il grado definito dagli archi

)

, … , ( ( )

di X. Siano le componenti connesse del grafo H(V,X) con archi e nodi di

1

∈ {1, … , }. ⊆ .

Prendo ora un indipendente massimale di S, Calcolata la sua

cardinalità, se questa non sarà dipendente da S, ma generica allora tutti gli indipendenti massimali

|( )|

( )| < − 1 ∈ {1, … , } ⇒ ∩

di X avranno la stessa cardinalità. Se |F∩ per qualche

) {}

( ⇒ ∃ ∈ \ ∶ ∪ ∈

non definisce un albero ricoprente di

S, cioè si può aggiungere un arco senza creare cicli e avere quindi un indipendente più grande ⇒

è (contraddizione). Quindi dovrà essere:

|( )|

∩ ( )| = − 1 ∀ ∈ {1, … , }

| , cioè un indipendente massimale in una componente

|( )| − 1 ∀

connessa ha un numero di archi pari esattamente a .

⇒ induce un albero ricoprente in ciascuna componente connessa di H(V,X). Considerando tutte

{=1}

|( )| ∑ |( )|

− 1 ∀ ∈ {1, … , } − 1 ∗ = −

le componenti connesse si ha quindi

||

⇒ = − : tale numero è indipendente da F quindi vale per ogni F indipendente massimale

in X, cioè per ogni base si ha la stessa cardinalità quindi lr(X)=r(X) e quindi S è una matroide.

Formulare un problema di MIS

Risolvere un problema di MIS (massimo insieme indipendente) vuol dire trovare max{c(F): F è un

dipendente di S} , cioè trovare F tale che sia massima la somma dei costi o vantaggi associati ad F.

Per risolvere problemi di questo tipo si possono usare due formulazioni: la formulazione rango e la

formulazione circuiti. Entrambe si possono applicare a qualunque problema reale come per

esempio ad un problema di aste combinatorie.

Ma cosa vuol dire formulazione? Innanzitutto definiamo vettore di incidenza un vettore a

|Γ|

{0,1} Γ.

componenti cioè un vettore che ha tante componenti quanti sono gli elementi di I

vettori di incidenza definiscono l’appartenenza di un insieme F all’insieme delle soluzioni

ammissibili S del sistema di indipendenza. Infatti tali vettori hanno la componente i-esima pari ad

1 se l’elemento i-esimo del vettore appartiene ad S, altrimenti hanno la componente pari a 0.

Quindi S si può esprimere anche attraverso l’insieme dei vettori di incidenza S:

|Γ|

{0,1}

{ ∈ : ∈ }

S=

Associare un vettore ad un insieme è un processo particolare che si chiama CODIFICA. D’ora in

avanti usare l’insieme S dato dagli insiemi F, oppure S dato dai vettori di incidenza di F sarà la

stessa cosa. ()

Avere una formulazione per risolvere un problema del tipo permette di evitare di

{∈S}

enumerare tutte le soluzioni per trovare quella ottima. Infatti se gli insiemi F sono tantissimi,

enumerare tutte le soluzioni richiede molto tempo ed elevati costi.

|Γ| |Γ|

{0,1}

= { ∈ : ≤ } ⇔ ∩ = S

Per definizione un poliedro è una formulazione di S ,

|Γ|

{0,1}

cioè se è in grado di dividere tutte le soluzioni S dalle non-soluzioni -S .

Quindi la formulazione è data dal poliedro mentre il rilassamento lineare è il problema che

risolviamo con la formulazione, cioè con il poliedro. Il rilassamento lineare è il problema rilassato.

∗

∈

Un vettore se il sistema definito da Ax≤ è soddisfatto da ogni componente del vettore,

∗ ∗

≤

cioè se per ogni componente di . Invece un vettore non appartiene al poliedro P se

viola almeno un vincolo del poliedro. Quindi appartiene al poliedro se li soddisfa tutti e non

appartiene se ne viola almeno uno. Ma costruire P è complicato! |Γ|

{0,1}

Quindi una formulazione è un poliedro che separa le soluzioni S dalle non-soluzioni -S .

Disequazioni valide e ridondanti

≤ ∈ S, ≤ ∀ ∈ S.

Una disequazione è valida se è soddisfatta da ogni cioè se Una

disequazione è valida se mantiene nel semispazio giusto le soluzioni ammissibili. Può contenere

anche le non-soluzioni, non fa niente. L’importante è che mantenga sempre le soluzioni amissibili,

sia valida.

≤ > .

Una disequazione si dice violata da se e solo se |Γ|

≤ = { ∈ : ≤

Una disequazione è ridondante per un poliedro P se e solo se

|Γ|

, ≤ } = { ∈ : ≤ } ≤ .

cioè se il poliedro resta lo stesso anche togliendo

Siano P e Q due formulazioni di S. Diciamo che P è migliore o equivalente a Q se e solo se P è

max{ : ∈ } ≤ max{ : ∈ } ∀

contenuto non propriamente in Q quindi se e solo se .

max{ : ∈ } ≤ max { : ∈ }

Inoltre si ha che quindi P è migliore di Q perché vogliamo il

più basso upper bound per S. P ci dà un rilassamento migliore rispetto a Q perché P è un poliedro

più piccolo di Q essendo contenuto in lui.

Si può dire che esiste una formulazione ottima, migliore di tutte le altre formulazioni e questa è ,

cioè: |Γ|

|Γ|

P = conv(S) = {y ∈ R : y = ∑ , ∈ }

S

{k=1}

|Γ|

∑ |Γ|}

= 1 ≥ 0 ∀ ∈ {1, … ,

Con , combinazioni convesse di S.

{=1}

è contenuta in ogni formulazione Q di S infatti:

max{ : ∈ } ≤ max { : ∈ } ≤ max { : ∈ } ∀ ∀

c

Quindi i verti