Ottimizzazione combinatoria 2 appunti

SET-COVERING:

Vediamo come si sceglie y come si aggiorna e come si trova una soluzione

x ammissibile. { }

= , … ,

1

⊆ è ⟺ ∩ è ∀ ∈

Cioè è un insieme che tocca tutti gli insiemi appartenenti alla famiglia I.

Insieme delle F non è un SI è uan qualunque famiglia di sottoinsiemi. T è un cover della famiglia se c’è un

elemento del cover in ogni insieme della famiglia esempio {3-6-10}, {4,5,8,13}

Ovviamente gli insieme di tutti i punti è un cover. Tende ad asssomigliare ad un complemento del SI.

Il problema di set-covering è detto anche HItting set, cioè colpisce ogni elemento della famiglia I.

()min

{() = ∑ ∶ è }

∈

Trovare il cover che ha peso più basso possibile (ovviamente il massimo cover non ha senso perché si

prende tutto j). Nei SI viceversa il minimo è l’insieme vuoto ||

2

Il numero di cover di una famiglia I è di ordine di grandezza , quindi esponenziale.

min

{(): ∑ : ⊆ è }

∈

∑ ≥ 1 , ∈

∈

formulazione naturale del SC :{ ≥ 0, ∈

||

{0,1}

∈ ∩ ⟺ :

vale sempre il vincolo che xe è minore o uguale di 1.

Si ha un vincolo per ogni elemento della famiglia F , cioè il vettore di incidenza di un cover deve avere

almeno una delle componenti pari a 1 per un elemento dell’insime F.

min

∑ ≥ 1 , ∈

∑ ≥ 1 , ∈

∈

: → : { ∈

≥ 0, ∈

≥ 0, ∈

||

{0,1}

∈

{

Quindi un set-covering è tale per cui T contiene almeno un elemento di ogni insieme I. quando la famiglia è

fatta da tantissimi insieme, il problema di cover diventa interessante e significativo. Ci sono solo due

possibilità un insieme o è un cover o non è un cover. Tra tutti i possibili cover si seleziona quello che pesa

meno. min

{(): ∑ : ⊆ è }

∈

problema difficile da risolvere con l’enumerazione completa.

|

è ∩ | ≥ 1 ∀ ∈

Cioè T è un cover se per ogni insieme di I la cardinalità dell’intersezione è almeno pari a 1.

Il vettore di incidenza del cover indica che se l’elemento appartiene a T allora è posto pari a 1

| ∩ | ≥ 1 ∀ ∈ ∑ ≥ 1 ∀ ∈

∈

Due insiemi hanno due vettori di incidenza. Con il prodotto interno dei due vettori, pari alla cardinalità, si

1 0

1 1

= =

[ ], [ ]

valuta il numero di elementi in comune 0 0

0 1

∙ =

La sommatoria è pari alla cardinalità! Cioè Si sommano solo gli elementi dove xF vale 1 del vettore xT.

∑ ≥ 1 ∀ ∈

Ogni vettore di incidenza xT di un cover T soddisfa il sistema ∈

Questo è un sistema di disequazioni perché si ha un’equazione per ogni F appartenente a I.

Quindi è un poliedro !

∈ il vettore di incidenza di un cover appartiene sempre alla famiglia di interi S

Viceversa il vettore di incidenza diun insieme A,che non è un cover non soddisfa almeno una disequazione

∑ ≥ 1 ∉ . Si hanno tutti gli elementi per dire che questa è un

∈

formulazione.

∑ ≥ 1 ∀ ∈

→ è

{ ∈

0 ≤ ≤ 1 ∀ ∈

Il poliedro separa i vettori 0-1 che ci interessano da quelli 0-1 che non interessano ma porta dentro tutti

quei vettori frazionari che non sono vettori di incidenza di un cover.

∑ ≥ 1 , ∈

∑ ≥ 1 , ∈

∈

: → : { ∈

≥ 0, ∈

≥ 0, ∈

||

{0,1}

∈

{

La famiglia è costituita da tutti i tagli s-t, tagli che separano s da t. insieme di archi che se tolti sconnetto s

da t. biosgna capire quali archi preservare per mantenere s-t connessi. Ogni taglio s-t deve contenere

almeno un arco di un cammino s-t.

Almeno un deve richiamare alla mente set-covering .

Altro problema di set covering: F è l’insieme di tutti i possibili tagli

Esempio più dettagliato: Crew Scheduling

Problema dei turni del personale. Occorre definire chi sono i piloti, le hostess, capo cabina ecc di uno

specifico volo. Sono problemi di tutti i giorni. Una generica azienda ha dei servizi da svolgere, nel caso della

compagnia aerea è coprire un segmento di volo

(volo dal punto di vista del passeggero), volare da

un aereoporto all’altro.

L’attività complessiva di un equipaggio può essere

formulata in infiniti modi. Il grafo ha come oggetti elementari i servizi.

Sequenze per le quali partenza e arrivo finale sono nella stessa città:

25.000 piloti e 1.5miliardi/anno per stipendi. Si suppone che i voli con gli orari siano già fissati. I segmenti

da scegliere su come stabilire le tratte è un altro problema di OC.

Fino al 92 l’algoritmo aggiustava le ottimizzazioni locali.

Dal 92 in poi si è utilizzata un’ottimizzazione globale.

8h di volo per ogni servizio e 12h di tempo totale di servizio. Il minimo tempo di sosta e riaggancio al volo

successivo dipende da quanto tempo si ha volato prima. Questo diagramma è un diagramma aereoporto –

tempo possibili accoppiamenti di voli con personale.

Ci si chiede come può essere formulato questo problema.

Occorre prima di tutto identificare gli <<eventi elementari>>, eventi dell’insieme gamma che vanno poi

messi insieme in soluzioni, vettore di componenti 0,1.

È sbagliato definire come evento elementare l’appartenenza o meno dei servizi al pairing. Somiglia alla

localizzazione degli impianti con pairing come impianto e servizio come cliente. Questa assegnazione porta

alla non costruzione del modello perché le condizioni di appartenenza sono difficili da esprimere (perché

bisogna codificare tutti gli accordi sindacali in vincoli) inoltre il costo del pairing dipende dai servizi che lo

compongono.

L’idea usata è generare molti pairing ammissibili con i rispettivi costi e poi scegliere l’insieme ottimo di

pairing che «copre» tutti i servizi risolvendo un problema di Set-Covering. Gli eventi elementari quindi

sono i pairing, le sequenze di servizio. Un servizio è una partenza da una città d’origine e una di

destinazione. { }

= , … ,

1

⊆ = ≪ ≫ ℎ

{4,5}

Esempio F8 contiene entrambi il servizio 8 8

I pairing devono essere scelti per coprire tutti i servizi. Il gioco è mettere inisieme i pairing in modo tale che

ogni servizio compaia almeno in un pairing generati. Quindi si realizza un certo numero di pairing e tra

questi si selezionano quelli per cui ogni servizio è coperto.

⊆J

Un cover è un Insieme di «pairing» T che interseca tutti gli insiemi Fk ovvero con la proprietà che ogni

servizio è contenuto in qualche «pairing» di T.

I costi da comparare sono differenti.

Ogni servizio deve stare esattamente in un paring: vincolo di uguaglianza. È un altro problema di OC molto

complicato, molto complicato anche trovare una soluzione ammissibile. si parla di set partitioning.

Problema di minimo quindi il duale è un problema di massimo. Ogni F corrisponde ai servizi da coprire. Si

vogliono trovare gli e che stanno in tutti i voli.

Il primale è il problema rilassato del problema PL01. Tutti i vettori dentro P se sono a componenti 0-1 sono

vettori di incidenza di un cover.

Nel vecchio 5 elementi e 8 voli … nel disegno è un caso più piccolo

Esempio l’equipaggio 4 vola su A e B.

≥ 1

Se per esempio ma poiché è o 0 o 1, viene fissato a 1.

5 5

Il pairing 5 quindi dovrà essere scelto per forza, ci deve essere per forza un equipaggio che fa il giro con i

voli A e C. questo porta ad eliminare il primo vincolo perché è x5 ad attivarlo.

L’obiettivo del duale è sommare tutte le y e trovare il valore massimo. I vincoli sulle Y derivano ad esempio

+ ≤ 1

domandandosi quale insieme F che contengono variabile 4: ya e yb e quindi

Una qualunque soluzione duale tutti 0 è un lower bound del primale.

Lezione 20

Teorema: (richiesta dimostrare il caso speciale del set covering)

̅ ∈ , ̅ ∈ ℎ:

̅ > 0 → ̅ = ̅ < →

̅ = 0)

(

Data

̅

̅ ∈ max −

Allora è una soluzione

̅ >0

Nel caso del set-covering si ha:

∈ ̅ è

-̅ | |

∩ ≥ 1 ∀ ∈

Ov