Appunti Ottimizzazione Combinatoria II

OTTIMIZZAZIONE COMBINATORIA II

Sistemi di indipendenza {1,2,

Γ = … , }

Un sistema di indipendenza è dato da un insieme base formato da n

, , … , } ⊆ Γ.

elementi e da un insieme delle soluzioni ammissibili S={ con

1 2

Appartengono ad un sistema di indipendenza e quindi all’insieme delle soluzioni

ammissibili S tutti gli insiemi di elementi che soddisfano una proprietà comune.

⊆

S quindi è un sistema di indipendenza se e solo se per un generico , si ha che

∈ . Per un sistema di indipendenza vale la proprietà di ereditarietà, cioè ogni

∈ ,

sottoinsieme di appartiene anche lui alla famiglia delle soluzioni S. Inoltre un

sistema di indipendenza deve sempre contenere l’insieme vuoto.

∈ S ∉ S

Quindi se l’insieme allora T è un indipendente in S. Se invece allora T è

un dipendente in S.

Inoltre, un sistema di indipendenza è definito da Basi e Circuiti: B è una Base di S se

∈ S ∧ ⊃ ∉ S; ∉ S ∧

e solo se T con C invece è un Circuito di S se e solo se

⊂ ∈ S.

con In alternativa si può dire che una base è l’insieme indipendente

massimale che si può avere in S mentre un circuito C è l’insieme dipendente

minimale in S , cioè C è un insieme dipendente e ogni suo sottoinsieme è

indipendente.

∈ ⟺ { ⊆ : S},

Quindi cioè se T è contenuto in qualche base di S

∈ ⟺ { è : S}

oppure cioè T non contiene

un circuito di S.

Esempi di sistemi di indipendenza

Un esempio di sistema di indipendenza è quello dato dagli insiemi stabili di un grafo

G(V,E). Gli elementi dell’insieme base in questo caso sono i nodi e l’insieme S delle

soluzioni ammissibili è dato dall’insieme dei nodi a coppie non adiacenti, cioè quelli

che non hanno archi in comune tra loro. In questo caso quindi i circuiti sono proprio

∈

gli archi E. Un insieme T è non stabile se e solo se contiene gli estremi di un

ℎ

arco. Invece una base è un insieme stabile massimale. Un insieme T quindi è una

base se e solo se non è contenuto propriamente in un altro insieme stabile.

L’insieme vuoto appartiene ad S perché se non ci sono nodi allora sicuramente non

ci sono coppie adiacenti. Vale l’ereditarietà in quanto se un insieme è indipendente

allora lo sarà anche un suo sottoinsieme in quanto si sceglie un sottoinsieme dei

nodi. Un caso particolare di insieme stabile è dato da un grafo senza archi: in questo

Γ 2

caso tutti i possibili sottoinsiemi di saranno insiemi stabili (sono quindi ).

Un altro esempio di sistema di indipendenza è dato dal matching di un grafo G(V,E),

cioè dall’insieme degli archi a coppie non incidenti nello stesso nodo. In questo caso

l’insieme base è costituito dagli archi del grafo (elementi=archi). I circuiti sono le

, ,

coppie di archi { } con archi incidenti nello stesso nodo. Di conseguenza T

ℎ ℎ

∉ ⇔

non è un matching e quindi ha almeno due archi incidenti nello stesso

nodo. Le basi invece sono i matching massimali che non sono propriamente

contenuti in un matching. L’insieme vuoto appartiene ad S perché se non ho archi

allora sicuramente non ne ho due incidenti nello stesso nodo. Vale l’ereditarietà.

Trovare il numero di matching in genere è più semplice di trovare il numero di

insiemi stabili. Un caso particolare di matching è quello in cui si ha un grafo non

connesso, quindi con un solo arco incidente in ogni nodo: in questo caso tutti gli

archi e i loro sottoinsiemi appartengono al sistema di indipendenza.

Un ulteriore esempio di sistema di indipendenza è dato dalle foreste di un grafo

G(V,E). In questo caso gli elementi dell’insieme base sono gli archi. Vale

∧ ⊆ ⇒

l’ereditarietà. Per definizione G(V,E) è una foresta E H(V,F) foresta, cioè il

grafo che si ottiene da una foresta considerando un sottoinsieme di archi della

foresta originaria, è ancora una foresta perché non si possono creare cicli se

prendiamo meno archi. Quindi un grafo G(V,F) è una foresta se e solo se F è una

foresta. I circuiti di questo sistema di indipendenza sono i cicli. Infatti per definizione

una foresta è un grafo senza cicli. L’insieme vuoto appartiene al sistema di

indipendenza in quanto se non ho archi allora non ho cicli. Le basi del sistema di

indipendenza delle foreste sono le foreste ricoprenti se il grafo non è connesso,

altrimenti sono gli alberi ricoprenti.

Consideriamo ora il sistema di indipendenza dato dall’insieme di vettori

Γ

linearmente indipendenti. In questo caso gli elementi di sono i vettori:

1 2

Γ = { , , … , } ⊆

∑

S ⇔ = 0 ⇒ = 0 ∀,

Un insieme di vettori Q∈ cioè i vettori sono

∈

linearmente indipendenti se il prodotto interno tra il vettore λ e la matrice formata

dai vettori è 0 solo se il vettore λ è 0 per ogni componente. I circuiti in questo caso

sono gli insiemi minimali di vettori linearmente dipendenti, cioè insiemi di vettori

linearmente dipendenti ma tali che ogni sottoinsieme è linearmente indipendente.

Le basi invece sono gli insiemi massimali di vettori linearmente indipendenti. Vale

l’ereditarietà e l’insieme vuoto appartiene ad S.

Un altro sistema di indipendenza è dato dall’insieme di progetti compatibili con un

budget. In questo caso gli elementi dell’insieme base sono i progetti. Si vuole

realizzare un numero di progetti in modo che le risorse utilizzate per realizzarli

soddisfino un determinato budget. C’è quindi un vincolo, detto vincolo di knapsack

3 + 2 + 4 ≤ 5

del tipo: . I coefficienti vicino alle variabili rappresentano le

1 2 3

risorse per realizzare il progetto i-esimo mentre il termine a destra della

disuguaglianza rappresenta il budget. Come è facile osservare, se si realizzano tutti i

≤ 5

progetti occorre un budget pari a 3+2+4= 9 che non è quindi gli indipendenti

sono le soluzioni di knapsack a coefficienti positivi. Non possono essere quelli a

coefficienti negativi perché se abbiamo un solo progetto che richiede risorse

negative, questo non è realizzabile. Se ho un gruppo di progetti che soddisfano il

vincolo di budget allora anche un suo sottoinsieme lo soddisferà quindi vale

l’ereditarietà (sempre per coefficienti positivi). Inoltre l’insieme vuoto appartiene al

sistema di indipendenza perché se non realizzo nessun progetto allora rientro nel

budget (non spendo nulla). In questo caso i circuiti sono gli insiemi di progetti non

compatibili con il budget ma tali che ogni sottoinsieme è compatibile. Le basi invece

sono gli insiemi di progetti compatibili massimale, cioè quelli per i quali la somma

dei coefficienti è inferiore o uguale al budget ma tali che con ogni progetto aggiunto

=1

si sfora il budget. Le variabili possono assumere due valori: se il progetto i

= 0

viene realizzato; se il progetto i non viene realizzato.

Il sistema di indipendenza costituito da sotto-sistemi di disequazioni lineari

ammissibili è un altro esempio di sistemi di indipendenza. In questo caso gli

elementi sono le singole disequazioni. I circuiti sono gli insiemi di disequazioni non

ammissibili ma tali che ogni sottoinsieme è ammissibile. Le basi invece sono gli

insiemi di disequazioni ammissibili massimale. Vale l’ereditarietà infatti se un

insieme è ammissibile allora lo sarà anche un suo sottoinsieme. L’insieme vuoto

appartiene al sistema di indipendenza perché l’insieme di disequazioni definisce un

poliedro e se non ci sono disequazioni il poliedro è tutto quindi è ammissibile in

tutto lo spazio.

L’ultimo esempio di sistema di indipendenza è dato dall’insieme degli archi la cui

rimozione non disconnette il grafo connesso G(N,A). Gli elementi dell’insieme base

S ⇔ (, − )

in questo caso sono gli archi del grafo. Un insieme T∈ resta

connesso, cioè il grafo che resta, togliendo gli archi di T, è ancora connesso.

L’insieme vuoto appartiene perché se non tolgo archi allora il grafo resta connesso.

Vale l’ereditarietà perché se tolgo un insieme di archi e il grafo resta connesso allora

lo sarà anche togliendo un insieme ancora più piccolo di archi. I circuiti sono i tagli

minimali, cioè quelli che non contengono propriamente un taglio. Le basi invece

sono i complementi di un albero ricoprente, cioè l’insieme di archi più grande che è

possibile togliere senza disconnettere il grafo, quindi l’insieme dato dagli archi che

non formano l’albero ricoprente.

WDP esempio

È un problema di ottimizzazione combinatoria. Si sceglie un sottoinsieme x (le

offerte accettate) delle offerte totali B che massimizza il valore degli oggetti in x,

max

cioè tale che: ; sotto il vincolo che ogni oggetto capiti al più una volta in x,

∑ ≤ 1 ∀

cioè lo stesso oggetto non si può vendere più di una volta: .

:∈

Inoltre, vale la regola del Free Disposal, cioè non si deve vendere tutto per forza.

Esempio asta combinatoria: si ha un numero di offerte per un gruppo di oggetti

diversi. La prima cosa da fare è verificare se c’è un sistema di indipendenza:

determinare gli elementi dell’insieme base e l’insieme base che in questo caso è

costituito dalle offerte; determinare S, cioè l’insieme delle soluzioni ammissibili che

è rappresentato dall’insieme delle offerte che non hanno oggetti in comune. Quindi

l’insieme vuoto appartiene al sistema perché non ha oggetti in comune con

nessuno, essendo vuoto. Vale l’ereditarietà. I circuiti sono le coppie di offerte che

hanno intersezione diversa da zero e, quindi hanno un arco tra loro, ma sono tali che

le singole offerte della coppia possono essere soddisfatte . Il sistema può essere

rappresentato mediante un grafo in cui i nodi sono le offerte e sono presenti archi

tra due offerte se queste hanno oggetti in comune. Quindi stiamo cercando

l’insieme stabile indipendente di massimo peso. Per determinare il vincitore

dell’asta: costruiamo il grafo delle offerte in cui ad ogni nodo corrisponde un’offerta

e in cui ci sono archi tra due nodi se questi hanno intersezione diversa da zero;

applichiamo l’algoritmo Greedy, quindi ordiniamo in ordine decrescente le offerte,

prendiamo la prima e la soddisfiamo; poi aggiungiamo solo le offerte che non hanno

oggetti già venduti; ci fermiamo quando non né più possibile soddisfare altre

offerte; la soluzione sarà data dalla somma delle offerte scelte. Vediamo se sono

basi se non si può aggiungere un altro nodo che non è adiacente a quelli già

considerati.

Rango e Lower rank ⊆ Γ}. Γ,

Dato un sistema di indipendenza S={: Sia X un qualsiasi sottoinsieme di non

necessariamente indipendente, e T un indipendente in S. T è un indipendente massimale e quindi

{}

⇔ ∪ ∉ S ∀ ∈ \. ⊆ Γ

una base di X In generale un sottoinsieme può contenere basi di

cardinalità diversa. Il rango di un insieme quindi è definito come la cardinalità dell’insieme

indipendente più grande costruibile in X, quindi come la massima cardinalità di una base di X:

{ ||: }.

r(X)= Il rango soddisfa alcune proprietà:

• ⊆ Γ;

r(0)=0 per X,Y

• ≤ () ⊆

r(X) , cioè il rango è non decrescente, aumenta all’aumentare della

dimensione dell’insieme;

• ∈ S ,

r(X)= |X| se e solo se cioè il rango è pari alla cardinalità se gli insiemi sono

indipendenti;

• ∧ ∀ ∈

r(X)= |X|-1 r(X-{e}) = |X| -1 se e solo se X è un circuito.

Il lower rank di un insieme invece è definito come la minima cardinalità di un indipendente

⊆ Γ,

massimale in quindi la cardinalità minima di una base di X: lr(X)= min{|B|: B base di X}.

⊆ Γ, ≤

Per ogni si ha che lr(X) r(X), cioè il lower rank è sempre minore o al più uguale al rango

⊆ Γ. ∀ ⊆ Γ

per un insieme Nel caso in cui lr(X)=r(X) allora si dice che S è una MATROIDE.

Nel caso degli insiemi stabili il rango viene anche chiamato “numero di stabilità” mentre nel

matching viene detto “matching number”. Nel sistema di indipendenza delle foreste invece il

rango può essere definito come il numero di archi in una foresta massimale F contenuta in A,

ovvero il numero di archi degli alberi ricoprenti delle componenti connesse di G(V,A). Per la

⊆ ,

pianificazione degli investimenti o knapsack invece il rango di un insieme A con N insieme dei

progetti totali realizzabili, è definito come il numero massimo di progetti compatibili con il budget

di un sottosistema di progetti A.

Massimo sottoinsieme indipendente MSI

È un problema di ottimizzazione combinatoria in cui vogliamo determinare max{ c(F): F è un

indipendente di S} con c(F) funzione obiettivo di F definita come somma dei costi o vantaggi degli

∑

∈ S:

elementi di F. S è un sistema di indipendenza ed F è un indipendente tale che F c(F)= ∈

∗

(vale il principio di sovrapposizione degli effetti). Ma trovare , cioè l’indipendente di massimo

peso, è difficile. Un importante teorema ci dice che se un elemento appartiene alla soluzione

∗ ∗ )

⇒ ( ≥ ()∀ ∈ S

ottima allora il suo costo non può essere negativo, cioè se è ottimo e

∈ ≥ 0

che ogni componente h ha la relativa componente di costo e quindi si possono

ℎ < 0 ⇒

eliminare gli elementi con peso negativo. La dimostrazione è banale infatti se ℎ

∗ ∗ ∗

)

( − {ℎ}) > (

e questo è assurdo perché ottimo e quindi non può essere minore di

un’altra soluzione per l’ereditarietà.

Algoritmo Greedy

L’algoritmo Greedy si applica ad un problema di massimo insieme indipendente del tipo max{ c(F):

F è un indipendente di S}. La funzione obiettivo c ordina le soluzioni e ci fa trovare la soluzione

migliore per l’algoritmo. Greedy trova soluzioni ragionevoli in quanto predilige le soluzioni che

pesano di più ma queste non sono necessariamente soluzioni ottime. Greedy produce soluzioni di

tipo euristico. L’algoritmo lavora in questo modo:

• , , … , } ≥ ≥ ⋯ ≥

Ordina gli elementi per peso decrescente : { :

1 2 1 2

• ≔ 0

Inizializza cioè a insieme vuoto

0

• ∪ { } ∈ S

Per ogni elemento i da 1 a n ho un insieme corrente , se allora aggiungi

−1

{ } ≔

l’elemento (quindi dal più pesante al meno pesante) e crea il nuovo insieme

∪ { ≔

} , altrimenti non aggiungere l’elemento e rinomina l’insieme

−1 −1

• oluzione

L’algoritmo termina con Greedy.

Quindi è un indipendente di S per come è stato costruito perché abbiamo aggiunto solo

elementi che appartenevano al sistema di indipendenza. Ogni a partire da è una sequenza di

0

insiemi indipendenti non necessariamente crescente perché non è detto che ad ogni passo

vengano aggiunti elementi. Inoltre è una base perché non si possono aggiungere altri elementi

ed avere ancora un indipendente altrimenti li avremmo aggiunti nell’algoritmo. La soluzione

∗

) )

( ≤ (

trovata dall’algoritmo sarà: , cioè non sarà necessariamente una soluzione ottima.

Greedy non garantisce l’ottimalità.

Una volta trovata la soluzione Greedy, il vero problema è verificare se questa sia ottima o meno. In

alcuni casi è possibile dire con certezza che la soluzione trovata è ottima come per esempio nel

caso in cui il sistema di indipendenza è una matroide.

Teorema di Jenkyns (76), Korte-Hausman (78)

Mette in relazione la struttura del sistema di indipendenza che ci viene dato e la soluzione Greedy,

cioè ci dice qual è la relazione tra la soluzione Greedy e la soluzione ottima del problema di

massimo insieme indipendente. La relazione è espressa attraverso un valore q( S) che dipende dal

sistema di indipendenza.

∗

)/( )

( ≤ 1 sempre ed in particolare il rapporto è uguale a 1 quando la soluzione Greedy è

la soluzione ottima. Il rapporto sarà tanto più piccolo quanto peggiore è il valore della soluzione

Gree