Telefono 0862433139 e-mail rossi@di.univaq.it Sito web

Ottimizzazione Combinatoria A. A. 2006-2007

Docente

Fabrizio Rossi Orario di ricevimento

mercoledi 17-19 oppure su appuntamento

Telefono 0862433139 e-mail rossi@di.univaq.it Sito web

http://www.di.univaq.it/~oil Orario delle lezioni

martedi ore 17.00 – 19.00 Aula 1.7 mercoledi ore 17.00 – 19.00 Aula 1.6 giovedi ore 11.30 – 13.30 Aula 2.4 Testi di riferimento

Base

A. Sassano, Modelli e Algoritmi della Ricerca Operativa, Franco Angeli Avanzati

L. A. Wolsey, Integer Programming, John Wiley & Sons, Inc.

W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial Optimization, Wiley

Materiale didattico sul sito http://www.di.univaq.it/~oil

Applicazioni

• Progetto di servizi logistici

• Progetto di una rete di trasmissione radiotelevisiva

• Gestione del servizio di trasporto urbano per handicappati

• Pianificazione della produzione

• Gestione delle partenze e degli arrivi in un

aeroporto

Progetto di servizi logistici

L’azienda di spedizioni Ex-press, proprietaria di alcuni treni merci, intende realizzare un servizio di

spedizioni tra L’Aquila e Pescara via ferrovia Pertanto:

1. Chiede gli orari disponibili alla società che gestisce la rete ferroviaria ( Rete Ferroviaria Italiana ) e i costi relativi

2. Configura il servizio che massimizza il guadagno Il gestore della rete

1. Studia la fattibilità delle richieste della società 2. Pianifica alcuni orari alternativi

3. Definisce i prezzi di ogni alternativa

Ex-press ha un problema di ottimizzazione

• Ex-press

Dati

Un insieme di orari O, ognuno con il proprio costo Un insieme di treni T, ognuno con il proprio

“profitto”

Problema

Assegnare un sottoinsieme T’
T di treni a un sottoinsieme di orari O’
O in modo da

massimizzare il guadagno (somma dei profitti –

somma dei costi) e rispettando i vincoli “fisici”

RFI ha un problema di ottimizzazione

• RFI

Dati

L’orario di nuovo treno

L’intervallo di tempo necessario a percorrere ogni tratta della linea

L’intervallo di tempo minimo e massimo di sosta in ogni stazione

Standard di sicurezza (due treni che viaggiano sulla stessa linea devono essere separati da almeno k metri, ecc.)

L’orario esistente Problema

Trovare (se esiste !) un orario che contenga il nuovo

treno e che rispetti gli standard di sicurezza

Problema di Ottimizzazione

E insieme ambiente (insieme di soluzioni, decisioni o alternative)

F  E insieme ammissibile

F è definito tramite un insieme di relazioni dette vincoli

f : E   funzione obiettivo

Direzione di ottimizzazione: minimo o massimo Problema di ottimizzazione (min)

Trovare un elemento x  F tale che f(x)
f(y)

 y  F.

v = f(x) valore ottimo

x soluzione ottima

Problema di Ottimizzazione Combinatoria

Dati

N insieme finito N = {1, 2, …, n}

c vettore di pesi c _j per ogni j
N Insieme ambiente

U = {tutti i possibili 2 ^|N| sottoinsiemi di N}

Insieme ammissibile

famiglia  di sottoinsiemi F di U Si definisce

Problema di Ottimizzazione Combinatoria min _S

_N {  j
S c _j : S
}

La definizione è analoga se si vuole massimizzare la

f.o.

Il problema dell’assegnamento

3 Artigiani 3 Lavori da realizzare

Tabella dei costi

Problema

Assegnare esattamente un lavoro ad ogni artigiano in modo da minimizzare i costi

10 15 12 2

14 7 10

1

3 2 1 A ^L

9

18

20

3

10 15 12 2

14 7 10

1

3 2 1 A ^L

9 18 20 3

Il problema dell’assegnamento

Insiemi ammissibili

1. {a

– l

, a

– l

, a

– l

} di costo 34

3. {a

– l

, a

– l

, a

– l

} di costo 37 4. {a

– l

, a

– l

, a

– l

} di costo 49 5. {a

– l

, a

– l

, a

– l

} di costo 28 6. {a

– l

, a

– l

, a

– l

} di costo 38 La soluzione ottima ha valore 28

I possibili assegnamenti sono n!, pertanto il numero di insiemi ammissibili è n!

2. {a

– l

, a

– l

, a

– l

} di costo 44

Il problema della bisaccia

Avete a disposizione un budget b per gli investimenti dell’anno 2002

Ad ogni progetto è associato - un costo a _j (> 0)

- un guadagno atteso c _j (>0) Problema

Scegliere l’insieme di progetti in modo che sia

massimizzato il guadagno atteso senza eccedere il

budget b

Il problema della bisaccia

4 1 8

12 4

14 3

10 2

c a

Insiemi ammissibili

, {1}, {2}, {3}, {4}, {1, 2}, {1, 4}, {2, 4}, {3,4}

Soluzione ottima {1, 2} di valore 24

Quanti sono gli insiemi ammissibili?

Il numero di possibili sottoinsiemi di un insieme di n oggetti è 2

. Se b =

a

/ 2 gli insiemi ammissibili sono almeno 2

1 2 3

Dimensione della bisaccia

b = 5

2

5 3

8 7

4 6 1

Il problema del commesso viaggiatore

n punti nel piano

Per ogni coppia di punti (i, j) si definisce un costo c

> 0 Problema

Trovare il “tour” di costo minimo

Il problema del commesso viaggiatore

2

8 5 7

4 6 1

3

Insiemi ammissibili: gli (n-1)!/2 possibili tour

Differenze e similarità

Proprietà fondamentali dei problemi di OC:

1. tutti i problemi di OC sono definiti su insiemi ammissibili finiti e numerabili

2. la funzione obiettivo è calcolabile in corrispondenza ad ogni insieme ammissibile

Quindi

esiste un algoritmo “universale” per i problemi di OC che si chiama ENUMERAZIONE TOTALE

Conclusione:

È inutile seguire questo corso

È vera questa affermazione?

4.02
10

1.07
10

1000000 31.62

9.97 1000

9.33
10

1.27
10

10000 10.00

6.64 100

3.6
10

1.02
10

100 3.16

3.32 10

n!

2

n

n

log n

n

Le operazioni eseguite da un moderno calcolatore (1 Ghz) in un anno sono pari a 3.15
10

Pertanto, per risolvere un problema di TSP con 20 città attraverso

l’enumerazione totale si impiegano circa 2 anni

1. Algoritmi ammissibili a complessità polinomiale [Assegnamento]

2. Algoritmi ammissibili a complessità pseudo polinomiali [Knapsack]

3. Algoritmi ammissibili a complessità non polinomiale [TSP]

4. Algoritmi approssimati a complessità polinomiale [Knapsack]

5. Algoritmi euristici [Knapsack, TSP]

Obiettivo del corso

Studiare tecniche matematiche che consentono di

progettare algoritmi “efficienti” per i problemi di OC

Che cosa si intende per algoritmo efficiente?

Obiettivo del corso

Modellare problemi decisionali derivanti da applicazioni del mondo industriale come

problemi di ottimizzazione

Parte I:

Insiemi indipendenti e coperture

(I Teoremi di Berge, König e Gallai)

Sommario

• Formulazioni ed esempi

• Insiemi indipendenti in un grafo

Insieme stabile

Abbinamento

• Coperture in un grafo

Insieme trasversale

Edge-cover

• Disuguaglianze duali deboli

• Il Teorema di König

• Il Teorema di Berge

• Il Teorema di Gallai

• Algoritmo per il matching

Il ballo

Problema 1. Il ballo (Berge)

• In una festa sono presenti n ragazzi e n ragazze.

• Ogni ragazzo scopre che sono presenti k sue fidanzate, ogni ragazza scopre che sono presenti k suoi fidanzati (k < n, k > 1)

Domanda

E’ possibile far ballare ciascun ragazzo con una delle sue

fidanzate e ciascuna ragazza con uno dei suoi fidanzati?

Formulazione

Alberto

Bruno

Claudio

Davide

Anna

Bice

Carla

Daniela

Il ballo. 4 ragazzi/e con 3 fidanzati/e

Le torri

Problema 2. Le torri

• Consideriamo una scacchiera n
n .

• Due torri si “danno scacco” se giacciono sulla stessa riga (colonna) della scacchiera.

Domanda

Qual è il massimo numero di torri che è possibile

disporre sulla scacchiera senza esse si diano scacco

reciproco?

A B C D 1

2 3 4

Formulazione

Due torri si danno scacco se si trovano sulla medesima riga o colonna:

A

B

C

D

1

2

3

Grafo intersezione 4

righe-colonne

La battaglia d’Inghilterra (1941)

Problema 3. La battaglia d’Inghilterra (Berge)

• Nel 1941 le squadriglie inglesi erano composte da aerei biposto, ma certi piloti non potevano formare una coppia per problemi di lingua o di abitudini.

Domanda

Dati i vincoli di incompatibilità tra coppie di piloti, qual è

il massimo numero di aerei che è possibile far volare

simultaneamente?

Alì

Bob

Charlie

David

Evgenij

Fëdor

Formulazione

Disegniamo il grafo di compatibilità dei piloti.

Alì Charlie

Bob

Evgenij

Abbinamento

In ognuno dei casi esaminati, la soluzione può rappresentarsi come un insieme A di spigoli di un grafo G = ( V , E ) a due a due non adiacenti

Tale insieme è detto abbinamento (matching)

Alberto Bruno Claudio

Davide

Anna Bice Carla Daniela

A B C D

1 2 3 4

Alì

Bob

David

Fëdor

Alì Charlie

Bob

Evgenij

Tipi di abbinamento

• Se | A | > | B | per ogni abbinamento B di G , allora A si dice massimo. La sua cardinalità si indica con μ( G)

Alberto Bruno Claudio

Davide

Anna Bice Carla Daniela

A B C D

1 2 3 4

Alì

Bob

David

Fëdor

Alì Charlie

Bob

Evgenij

• Se G è bipartito, anche A si dice bipartito

• Se | A | = | V |/2, allora A si dice perfetto

Insieme indipendente

Definizione:

Dato un grafo simmetrico G = ( V , E ), si dice indipendente un

qualunque sottoinsieme S di vertici ( A di spigoli) costituito da elementi a due a due non adiacenti.

• L’insieme S è detto stabile (stable set).

• L’insieme A è detto abbinamento (matching).

Definizione:

Un insieme indipendente X si dice massimale se ogni elemento di

V – X (di E – X ) risulta adiacente ad almeno un elemento di X .

Un insieme indipendente X* si dice massimo se | X* | > | X | per ogni

insieme indipendente di G .

Esempi

Osservazione: Ø è indipendente

stabile massimale

Esempi

stabile massimale, ma non massimo

abbinamento massimale

Esempi

stabile massimale, ma non massimo

abbinamento massimale, ma non massimo

Copertura

Definizione:

Dato un grafo simmetrico G = ( V , E ), diremo copertura un qualunque sottoinsieme T di vertici ( F di spigoli) tale che ogni spigolo di E (vertice di V ) incide su almeno un elemento di T (di F ).

• L’insieme T è detto trasversale (vertex-cover).

• L’insieme F è detto edge-cover.

Definizione:

Una copertura X si dice minimale se X – { x } non è una copertura, per ogni x
X .

Una copertura X* si dice minima se | X* | < | X | per ogni copertura di

G .

Esempi

Osservazione: V e E sono rispettivamente trasversale e edge-cover

trasversale minimale

Esempi

trasversale minimale, ma non minimo

edge-cover minimale

Esempi

trasversale minimale, ma non minimo

edge-cover minimale, ma non minimo

Disuguaglianze duali deboli

D’ora in avanti indicheremo la cardinalità di:

• un insieme stabile massimo di G con il simbolo
( G )

• un abbinamento massimo di G con il simbolo μ( G )

• uno edge-cover minimo di G con il simbolo ( G )

• un insieme trasversale minimo di G con il simbolo ( G ).

Teorema Per ogni grafo G valgono le seguenti diseguaglianze:

( G ) < ( G ) μ( G ) < ( G )

(diseguaglianze duali deboli).

Disuguaglianze duali deboli

Dimostrazione

Siano rispettivamente X _ V , Y _ E un insieme indipendente e una copertura di G .

Poiché Y copre V , ogni elemento x di X incide su almeno un elemento y di Y .

D’altronde nessun y
Y copre contemporaneamente due elementi di X , altrimenti questi sarebbero adiacenti, e dunque X non sarebbe

indipendente.

Quindi esiste un distinto y
Y per ogni x
X , e di conseguenza | X | < | Y |

Riscrivendo questa relazione per X* e Y* si ottiene

( G ) < ( G )

Scambiando poi il ruolo di V ed E si ottiene

μ( G ) < ( G )

Disuguaglianze duali deboli

Esempio

trasversale e

abbinamento

Disuguaglianze duali deboli

Esempio

Forse valgono sempre con il segno “=“ ?

stabile ed

edge-cover

Disuguaglianze duali deboli

Esempio

Forse valgono sempre con il segno “=“ ?

NO!!!

Teorema (Gallai 1959).

Per ogni grafo G con n nodi si ha:

(G) + (G) = n (1) Se inoltre G non ha nodi isolati

μ(G) + (G) = n (2)

Teorema di Gallai

Esempio (1)

Teorema di Gallai

Esempio (2)

Teorema (Gallai 1959).

Per ogni grafo G con n nodi si ha:

(G) + (G) = n (1) Se inoltre G non ha nodi isolati

μ(G) + (G) = n (2)

Dimostrazione (I)

Dimostrazione:

(1) Sia S stabile in G . Allora V – S è un trasversale di G

S

Se |S*| =
(G), allora (G) < |V – S*| = n –
(G) .

Viceversa, se T è un trasversale, V – T è stabile in G

Posto quindi (G) = |T*| ^{, si ha}

(G) > |V – T*| = n – (G)

che insieme a

(G) < |V – S*| = n –
(G)

dimostra

(G) = n – (G)

T

non coperto da T

Dimostrazione (II)

(2) G privo di nodi isolati, A abbinamento di G , V _A insieme dei nodi saturi rispetto ad A

V _A

H insieme minimale di archi di G tale che ogni nodo in V – V _A è estremo di qualche arco in H.

|H| = |V – V _A | = n – 2 |A|

Osservazione:

C = A
H è un edge-cover

Dimostrazione (III)

Quindi

1. Scelgo un abbinamento A di cardinalità pari a μ(G)

2. Costruisco l’insieme C = A
H

Dimostrazione (IV)

Poiché C è un edge-cover, si ha |C| > (G)

Pertanto

(G) < |C| = |A| + |H| = n – μ(G)

Dimostrazione (V)

Sia C un edge-cover di G , con |C| =
^(G)

Sia H = (V, C) il sottografo indotto da C

Valgono le seguenti proprietà:

1) H è un grafo aciclico

Difatti, se H contenesse cicli allora C non sarebbe un edge-

cover minimo (l’arco rosso di figura può essere rimosso)

Dimostrazione (VI)

2) Ogni cammino in H ha al più 2 spigoli

Difatti, se esiste un cammino con 3 spigoli, posso rimuovere

sempre un arco in modo da avere un edge-cover, contraddicendo il fatto che C è minimo

Osservazione

Dalle proprietà 1) e 2) deduco che H è un grafo costituito da n

vertici,
^(G) spigoli, decomponibile in N componenti componenti

connesse aventi la forma di “stella”

Dimostrazione (VII)

Consideriamo la componente i -esima di H

In generale, essa avrà ha s _i nodi e s _i – 1 archi Quindi

1<i<N s _i = n

1<i<N (s _i – 1) =
1<i<N s _i – N =
^(G).

Allora N = n – (G) .

Sia A un abbinamento con uno spigolo per ogni componente di H.

Si ha

μ(G) > |A| = n – (G)

che con (G) < n – μ(G) fornisce la tesi.

Formulazioni di PLI: Massimo Stabile

n i

x

E j

i x

x

x

S i

x

i

j i

n

i

i i

,..., 1

}, 1 , 0 {

) ,

(

1 st

max

altrimenti

0

vertice il

se 1

1

=







+





Dati

G ( V, E ) , | V |= n, | E |= m

Variabili decisionali

Formulazione

Rilassamento Lineare

n i

x

E j

i x

x

x

i

j i

n

i

i

,..., 1

, 0

) ,

(

1 st

max

1

=







+

 =

Osservazione:

La limitazione x

< 1 può essere omessa

Indichiamo con

⁽ G ) il valore della soluzione ottima del rilassamento lineare

STAB

Formulazioni di PLI: Minimo edge-cover

m e

y

V i

y

y

C e

y

e

e i

e

E e

e e

,..., 1

}, 1 , 0 {

1

st

min

altrimenti

0

arco l'

se 1

) (

=



















Variabili decisionali

Formulazione

Rilassamento lineare

m e

y

V i

y

y

e

e i

e

E e

e

,..., 1

, 0

1

st

min

) (

=















Osservazione:

La limitazione y

< 1 può essere omessa

Indichiamo con

( G ) il valore della soluzione ottima del rilassamento lineare

EDGE-C

Dualità

Osservazione:

STAB

e EDGE-C

costituiscono una coppia primale-duale

Inoltre:

⁽ G ) <

( G )



( G ) <  ⁽ G )

Allora:

⁽ G ) <
_RL ⁽ G ) =  _RL ⁽ G ) <  ⁽ G )

Formulazioni di PLI: Massimo Matching

m e

y

n i

y

y

A e

y

e i e

e E e

e e

,..., 1

}, 1 , 0 {

,..., 1

1

st

max

altrimenti

0

arco l'

se 1

) (

=



=













Variabili decisionali

Formulazione

Rilassamento Lineare

max y

e E



st

y

e ( i)


1 i = 1,..., n y

 0, e = 1,..., m

Osservazione:

La limitazione y

< 1 può essere omessa

Indichiamo con μ

( G ) il valore della soluzione ottima del rilassamento lineare

MATCHING

Formulazioni di PLI: minimo trasversale

n i

x

E j

i x

x

x

T i

x

i

j i

n

i

i i

,..., 1

}, 1 , 0 {

) ,

(

1 st

min

altrimenti

0

vertice il

se 1

1

=







+



 =

Variabili decisionali

Formulazione

Rilassamento lineare

n i

x

E j

i x

x

x

i

j i

n

i

i

,..., 1

, 0

) ,

(

1 st

min

1

=





+

 = TRASV

Osservazione:

La limitazione x

< 1 può essere omessa

Indichiamo con

( G ) il valore della soluzione

ottima del rilassamento lineare

Dualità

Osservazione:

MATCHING

e TRASV

costituiscono una coppia primale-duale

Inoltre:

μ ⁽ G ) < μ

( G )

( G ) <
⁽ G )

Allora:

μ ⁽ G ) < μ _RL ⁽ G ) =
_RL ⁽ G ) <
⁽ G )

Cammino alternante

Sia A un abbinamento di G

Definizioni

• Uno spigolo ( i , j ) di G si dice accoppiato (libero) se ( i , j ₎
A (( i , j _{) } A ).

• Un vertice i di G si dice accoppiato (esposto) se su di esso incide (non incide) uno spigolo di A

• Un cammino P di G si dice alternante rispetto ad A se è

costituito alternativamente da spigoli accoppiati e liberi.

Cammini aumentanti

Definizione

Un cammino P alternante rispetto ad A che abbia

entrambi gli estremi esposti si dice aumentante

“Aumentare” un abbinamento

Teorema

Sia A un abbinamento di G e sia P un cammino aumentante. La differenza simmetrica

A ’ = ( A – P _)
( P – A ) = A _ P

è un abbinamento di cardinalità | A | + 1.

A-P

P-A P-A

Dimostrazione (I)

Sia A un abbinamento di G e sia P un cammino alternante rispetto ad A che sia anche aumentante. L’insieme

D = ( A – P _)
( P – A ) gode delle seguenti proprietà

1) è un abbinamento

Difatti, se D non fosse un abbinamento allora esisterebbero almeno due spigoli di D tra loro adiacenti. Questi due spigoli

1. Non possono appartenere entrambi ad A perché A è un abbinamento.

2. Non possono appartenere entrambi a P perché P è alternante.

Ma se uno di essi è in A e l’altro è in P, allora devono

necessariamente appartenere a P , contro la definizione di D .

A – P

2) ha un elemento più di A Difatti:

Dimostrazione (II)

P – A

Teorema di Berge

Teorema (Berge, 1957) Un abbinamento A di G è massimo se e solo se G non ammette cammini alternanti rispetto ad A che siano anche aumentanti.

Dimostrazione

Condizione necessaria:

dal Teorema precedente, se esiste in G un cammino

aumentante rispetto A , allora esiste un abbinamento di

cardinalità | A | + 1, quindi, A non è massimo.

Teorema di Berge

Dimostrazione

Condizione sufficiente:

dimostro che se A non è massimo allora esiste un cammino aumentante in G rispetto ad A .

Sia B un abbinamento di G con un elemento più di A .

Consideriamo il sottografo G’ di G individuato dall’insieme di archi

F = ( A _ B ) / (A
B) e da tutti i loro estremi.

Poiché A e B sono abbinamenti, i vertici di G’ hanno grado <

2.

Quindi le componenti connesse di G’ sono percorsi o cicli.

Teorema di Berge

Nessun ciclo può essere dispari

altrimenti A o B non sarebbero abbinamenti

Non tutti i percorsi sono pari altrimenti | A | = | B |

Quindi, senza perdere di generalità, esiste un percorso con un numero dispari di archi che inizia e termina con archi di B

Tale percorso è evidentemente aumentante rispetto ad A

Un possibile algoritmo

A =
; //Inizializzazione trovato = TRUE;

while (trovato) {

search (A, &trovato);

if (trovato)

aumenta (G, &A);

}

Come è fatta search (G, A, &trovato)?

Teorema del cammino aumentante Teorema

Sia v un vertice esposto in un abbinamento A . Se non esiste un cammino aumentante per A che parte da v , allora esiste un

abbinamento massimo avente v esposto

Dimostrazione

Sia A * un abbinamento massimo in cui v è accoppiato.

Consideriamo A
A *.

Dimostrazione

Poiché A e A * sono due abbinamenti e v è accoppiato in A* , si ha che A
A* non può contenere un cammino

v

perché aumentante per A .

Pertanto, scambiando gli spigoli verdi con quelli rossi, posso ottenere da A* un altro abbinamento massimo, ma con v esposto.

v

Però, contiene un cammino

Un possibile algoritmo (II)

A = ; trovato = FALSE; //Inizializzazione for (v
V) {

if (v è esposto) {

search (v, A, &trovato, &q);

if (trovato)

aumenta (q, v, &A);

else

//cancella v e tutti gli

//spigoli incidenti in v cancella (v, &G);

}

Scopo della funzione search

trovare un cammino aumentante rispetto A, oppure dire che non esiste

Parametri

v nodo esposto, A abbinamento,

trovato, variabile booleana

q , vertice estremo del cammino aumentante Introduciamo un’etichetta per i vertici di V

label (w) = PARI

= DISPARI

= NULL

Ricerca di cammini aumentanti

search (v, A, *q, *trovato) { for (i
V)

label (i) = NULL;

LIST = {v};

label {v} = PARI;

while (LIST != ) { pop (&i, LIST);

if (label (i) == PARI)

esplora_pari (i, A, q, trovato,

&LIST);

else

esplora_dispari (i, A, &LIST);

if (trovato) return;

} }

Ricerca di cammini aumentanti (II)

Ricerca di cammini aumentanti (III)

esplora_pari (i, A, *q, *trovato, *LIST) { for (j
(i)) {

if (j  A) {

*q = j;

*trovato = TRUE;

pred (q) = i;

return;

}

if (j
A && label (j) == NULL) { pred (j) = i;

label (j) = DISPARI;

push (j, LIST);

} }

}

Ricerca di cammini aumentanti (IV)

esplora_dispari (i, A, *LIST) {

j = vertice accoppiato ad i in A;

if (label (j) == NULL){

pred (j) = i;

label (j) = PARI;

push (j, LIST);

}

}

Esempio

v , PARI

DISPARI DISPARI DISPARI

PARI PARI PARI

q , ESPOSTO

Sia A il matching rosso

Esempio

v , PARI

DISPARI DISPARI DISPARI

PARI

PARI PARI

Sia A il matching rosso

Esempio

v

q

Un problema

v, P D

D

D P

P

D oppure P ?

Correttezza Teorema

Se i vertici di G sono etichettati in modo “unico” dalla procedura search rispetto ad un abbinamento A,

allora search termina con un cammino aumentante, se esso esiste.

Domanda

Esistono grafi che ammettono sempre la proprietà di

unicità delle etichette?

Grafi bipartiti

G ( X , Y , E ) grafo bipartito

Teorema di König

Teorema (König 1931).

Se G = (X, Y, E) è un grafo bipartito allora μ(G) =
(G) Dimostrazione

Sia A un abbinamento massimo, e siano

X

: insieme dei nodi x di X saturi rispetto ad A

X

: insieme dei nodi x di X esposti rispetto ad A

Teorema di König

X ₁

X ₂

Nodi raggiungibili

Definizione : Un nodo y
Y

è raggiungibile se esiste P alternante rispetto ad A da x in X

tale che l’ultimo arco non appartiene ad A

Y

: insiemi dei nodi y di Y raggiungibili da x in X

Osservazione

Per definizione i nodi in Y

sono saturi, altrimenti A non sarebbe massimo

Infine: Y

: Y – Y

X ₁

X ₂

Teorema di König

Y ₁

Y ₂

X ₁

X ₂

Teorema di König

Consideriamo il seguente insieme di nodi

Z = {z

, z

, …, z

} con z

= y

se y

è raggiungibile z

= x

altrimenti

e dimostriamo che è un trasversale

Y ₁

Y ₂

Dimostrazione (I)

X ₁ Y ₁

Y ₂ X ₂

Dimostriamo che non esistono archi da nodi in X

verso nodi in Y non coperti da Z. Difatti,

1) Non può esistere un arco non coperto da Z tra un nodo in X

e un nodo in Y

, altrimenti il matching non sarebbe massimo

2) Non può esistere un arco non coperto da Z tra un nodo in X

e un nodo in Y

perché i nodi in Y

sono raggiungibili e quindi l’arco sarebbe coperto

1

2

Dimostrazione (II)

X ₁ Y ₁

Y ₂ X ₂

Dimostriamo che non esistono archi da nodi in Y

verso nodi in X

non coperti da Z.

Difatti, consideriamo l’arco 1, da X

a Y

. Se non fosse coperto

significa che il nodo y

, estremo dell’arco del matching è raggiungibile.

Ma allora esisterebbe un cammino aumentante e il matching non sarebbe massimo.

1

y

Dimostrazione (III)

X ₁ Y ₁

Y ₂ X ₂

Consideriamo un arco da X

a Y

, ad esempio l’arco 2.

Se non fosse coperto significa che il nodo y

non è raggiungibile, ovvero non appartiene ad Y

(contraddizione).

y

y

x

2

Pertanto Z è un trasversale di cardinalità pari a μ(G).

Parte II:

Ottimalità, rilassamenti e bound

Sommario

• Definizioni di bound “primali” e “duali”

• Rilassamento di un problema di OC

• Esempi di rilassamenti per il problema del TSP

Il rilassamento 1-albero

Il rilassamento 2-abbinamento

• Bound primali per il TSP

Nearest Neighbor e Insertion

Algoritmi approssimati (Double Tree, Christofides)

• Bound dal rilassamento lineare

Il rilassamento lineare del knapsack

Bound primali: algoritmo greedy

• Bound per dualita

• Formulazioni di PL

• Formulazioni ideali e matrici TU

Ottimalità, rilassamenti e bound

Consideriamo il seguente problema

z

= max {c

x : x
X, X  {0,1}

} z* è il valore della soluzione ottima x*.

Domanda

In che modo è possibile certificare che la soluzione x* è ottima?

In generale, se disponessimo di un algoritmo che genera le due sequenze di soluzioni:

z

> z

> …> z

> z*

z

< z

< …< z

< z*

Potremmo fornire come criterio di arresto

z

- z

<  (> 0)

Lower (upper) bound

Bound “primali”

Ogni soluzione x
X ammissibile è un lower ( upper ) bound per un problema di massimizzazione (minimizzazione)

z*

z

z

z*

z

z

Upper (lower) bound

Bound “duali”

Al contrario dei bound “primali”, trovare upper (lower) bound di buona qualità per problemi di massimo (minimo) è tipicamente difficile

Buoni bound “duali” si ottengono attraverso lo studio delle proprietà strutturali del problema di OC

Le proprietà di un problema di OC si caratterizzano tramite

1. Rilassamenti del problema

2. Definizione e studio di problemi “duali”

Rilassamento

Definizione

Il problema

(RP) z

= max {f(x) : x
T, T  R

} (z

= min {f(x) : x
T, T  R

}) si definisce rilassamento del problema

(P) z = max {c

x : x
X, X  {0,1}

} (z = min {c

x : x
X, X  {0,1}

}) se e solo se:

i) X  T

ii) f(x) > c

x per ogni x
X (f(x) < c

x per ogni x
X)

Proprietà 1. Se RP è un rilassamento di P, allora z

> z

(z

< z

)

Proprietà 2. Se x

sol. ottima di RP è ammissibile per P allora x

= x

Esempi di rilassamenti

Problema del commesso viaggiatore (simmetrico) Dati: grafo G=(V,E), pesi sugli archi c

per ogni arco e
E Domanda: trovare il ciclo hamiltoniano di peso minimo

Definizione: Un 1-albero è un sottografo di G consistente di due archi

adiacenti al nodo 1 più gli archi di un albero ricoprente i nodi {2, …, n}

Esempio

1

2

3

5

4

Rilassamenti per il TSP

Osservazione

Un ciclo hamiltoniano è un particolare 1-albero 1

2

3

5

Pertanto, il problema 4

Dati: grafo G = (V,E), pesi sugli archi c

per ogni arco e
E Domanda: trovare l’1-albero di peso minimo

è un rilassamento del problema del TSP, perché l’insieme X di tutti i cicli

hamiltoniani è  nell’insieme T di tutti gli 1-alberi

Definizione

Un 2-abbinamento è un insieme di archi tali che …

Rilassamenti per il TSP

1

2

3

6

4

5

Rilassamenti per il TSP

Osservazione

Un ciclo hamiltoniano è un particolare 2-abbinamento, difatti è un 2- abbinamento privo di sottocicli (subtour)

5 1

2

3

6

4 Pertanto, il problema

Dati: grafo G = (V,E), pesi sugli archi c

per ogni arco e
E Domanda: trovare il 2-abbinamento di peso minimo

è un rilassamento del problema del TSP, perché l’insieme X di tutti i cicli

hamiltoniani è  nell’insieme T di tutti i 2-abbinamenti

Un esempio

- 99

99 1

1 6

10 -

1 1

99 99

5

99 1

- 1

99 99

4

99 1

1 -

10 99

3

1 99

99 10

- 1

2

1 99

99 99

1 -

1

6 5

4 3

2 1

Consideriamo la seguente istanza del

problema del Commesso Viaggiatore:

Un esempio

1

2

3

6

4

5

- 99

99 1

1 6

10 -

1 1

99 99

5

99 1

- 1

99 99

4

99 1

1 -

10 99

3

1 99

99 10

- 1

2

1 99

99 99

1 -

1

6 5

4 3

2

1

Un esempio

1

2

3

6

4

5

- 10 99

99 1

1 6

10 -

1 1

99 99

5

99 1

- 1

99 99

4

99 1

1 -

10 99

3

1 99

99 10

- 1

2

1 99

99 99

1 -

1

6 5

4 3

2 1

Il 2 abbinamento di peso minimo

ha valore 6

Un esempio

1

2

3

6

4

5

- 10 99

99 1

1 6

10 -

1 1

99 99

5

99 1

- 1

99 99

4

99 1

1 -

10 99

3

1 99

99 10

- 1

2

1 99

99 99

1 -

1

6 5

4 3

2 1

L’1-albero di peso minimo ha

valore 15

Un esempio

1

2

3

6

4

5

- 10 99

99 1

1 6

10 -

1 1

99 99

5

99 1

- 1

99 99

4

99 1

1 -

10 99

3

1 99

99 10

- 1

2

1 99

99 99

1 -

1

6 5

4 3

2 1

Il ciclo hamiltoniano di peso

minimo ha valore 24

Un esempio (2)

1

2

3

6

4

5

- 5

99 99

1 1

6

5 -

10 1

99 99

5

99 10

- 10 99

99 4

99 1

10 -

5 99

3

1 99

99 5

- 1

2

1 99

99 99

1 -

1

6 5

4 3

2 1

Il 2 abbinamento di peso minimo

ha valore 24

Un esempio (2)

1

2

3

6

4

5

- 5

99 99

1 1

6

5 -

10 1

99 99

5

99 10

- 10 99

99 4

99 1

10 -

5 99

3

1 99

99 5

- 1

2

1 99

99 99

1 -

1

6 5

4 3

2 1

L’1-albero di peso minimo

ha valore 19

Un esempio (2)

1

2

3

6

4

5

- 5

99 99

1 1

6

5 -

10 1

99 99

5

99 10

- 10 99

99 4

99 1

10 -

5 99

3

1 99

99 5

- 1

2

1 99

99 99

1 -

1

6 5

4 3

2 1

Il ciclo hamiltoniano di peso

minimo ha valore 32

Ricapitolando…

Abbiamo definito per il TSP due lower bound con le seguenti proprietà:

1. Sono lower bound “combinatori”, ovvero si ottengono tramite la soluzione di un problema di OC

2. Tutti e due i problemi la cui soluzione genera i lower bound sono “facili”, ovvero hanno complessità polinomiale

La proprietà 2. è una proprietà chiave per ogni bound duale

Difatti, se il calcolo del bound fosse un problema NP-completo sappiamo che calcolare il bound diventa almeno tanto difficile quanto risolvere il problema stesso.

Domanda

Come si possono calcolare bound primali (ovvero soluzioni ammissibili di

buona qualità) per il problema del TSP?

Algoritmi euristici

Un algoritmo A si dice euristico per un problema P se restituisce una soluzione ammissibile z ^A che non è garantito essere la soluzione ottima.

Sia P problema di minimizzazione. Un algoritmo euristico si dice
-approssimato se

1. Ha complessità polinomiale

2. Per ogni istanza I di P con soluzione ottima z *( I ), si ha

z ^A ( I ) / z *( I _{) <}
(1)

Osservazione: se P è problema di massimo
< 1 e (1)

vale con il segno di >

Euristiche per il TSP

G = ( V , E ) grafo completo c _uv costo dell’arco uv
E

Euristiche costruttive: tentano di costruire un “buon”

ciclo hamiltoniano a partire da un sottociclo eventualmente vuoto.

Euristiche migliorative: a partire da una soluzione

ammissibile, si tenta di migliorarla attraverso

miglioramenti “locali”.

Euristica Nearest Neighbor

Input: G =( V , E ) Output: ciclo hamiltoniano T

procedure nearest_neighbor ()

Scegli un vertice u
V qualsiasi;

W = V \ {u}, aggiungi u alla lista T

while |W| > 0 {

scegli v
W tale che c

= min {c

: j
W}

Aggiungi {v} alla lista T W = W \ {v}

u = v

}

Esempio Nearest Neighbor

1000

2

1 2

5 4

Soluzione di valore 1005, è ottima?

Esempio Nearest Neighbor

1000

2

1 2

5 4

La soluzione ottima vale 12

Osservazione: il rapporto z ^A ( I )/ z *( I ) può essere reso

grande a piacere.

Euristiche di inserimento

Euristiche di inserimento

Euristiche di inserimento

Euristiche di inserimento

Input: G =( V , E ) Output: ciclo hamiltoniano T

procedure insertion_heuristic ()

Inizializza T con un sottociclo W = V /T;

while (|W| > 0) {

scegli un vertice u
W;

scegli la posizione in cui inserire u in T;

inserisci u in T;

elimina u da W;

}

Selezione del vertice da inserire

Definizione

Si definisce distanza di un vertice u da un ciclo T, il peso del più piccolo spigolo che collega il vertice ad un altro qualsiasi vertice del ciclo

T = (1, 2, .., k )

dist ( u , T ) = min { c _uv : v
^{C }}

Nearest Insertion

Inserisci il vertice u che minimizza dist ( u , T ), u _ T Farthest Insertion

Inserisci il vertice u che massimizza dist ( u , T ), u _ T

Selezione della posizione di inserimento

Osservazione

Scegliere la posizione equivale a scegliere lo spigolo da eliminare nel ciclo T . Un vertice può essere inserito in ogni posizione di T .

Sia T = ( v ₁ , v ₂ , …, v _n ) , c ( T ) il suo costo e sia u lo spigolo da aggiungere al ciclo

Se c ( T ( i )) è il costo del ciclo ottenuto da T inserendo nella posizione i il nodo u, il costo di inserimento è pari a c ( T ( i )) - c ( T ).

Si seleziona la posizione che minimizza c ( T ( i )) - c ( T )

Esempio

7

9

6 14 9 2

5

3

12 1

d = 7

d = 1

Esempio

7

9

6 14 9 2

5

3

12 1

d = 7

d = 12 2

3 1

T = {1, 2, 3}

Esempio

7

9

6 14 9 2

5

3

12 1

2

3 1

C = 21

Esempio

7

9

6 14 9 2

5

3

12 1

2

3 1

C = 16

Esempio

7

9

6 14 9 2

5

3

12 1

2

4 1

C = 7

3

Altre regole di selezione del vertice

Random Insertion: si sceglie un vertice a caso fra quelli non ancora inseriti nel ciclo

Cheapest Insertion: si sceglie il vertice che può essere

aggiunto al ciclo con il minimo aumento di costo

Una proprietà strutturale

Si dice che la matrice delle distanze di un grafo G soddisfa la disuguaglianza triangolare se

comunque prendo un triangolo e ₁ , e ₂ , e ₃ in G si ha c _ei + c _ej > c _ek per i
j
k , i , j , k  {1, 2, 3}

5

4

7 6

5 4

Richiamo

G = ( V , E ) è un grafo euleriano se e solo se il grado di ogni nodo è pari

Se G = ( V , E ) è un grafo euleriano e v è un vertice di G allora è possibile costruire un percorso che inizia e finisce in v e che attraversa ogni spigolo esattamente una volta

Teorema

Sia H = ( V , F ) un grafo completo con la matrice dei costi che soddisfa la disuguaglianza triangolare. Sia G = ( V , E ) un sottografo euleriano connesso di H . H contiene un

ciclo hamiltoniano di lunghezza al più  _e
E ^c _e

Dimostrazione (idea)

1

2

3

4

5

Euristica Double Tree

1. Calcola un minimo albero ricoprente K

2. Raddoppia gli spigoli di K, formando un percorso euleriano

3. Ricava un ciclo hamiltoniano dal percorso euleriano Indichiamo con z ^H _DT il valore della soluzione che si

ottiene applicando l’euristica Double Tree

Da un percorso euleriano ad un ciclo hamiltoniano

Consideriamo un percorso euleriano ( v ₁ , …, v _k )

procedure obtain_hamiltonian () T = {v

}, i=2, v = v

while |T| < n { if v

 T

T = T
{v

} collega v a v

v = v

i ++

}

collega v a v

T è un ciclo hamiltoniano

Esempio

1 2

3

4

5

6 7

11 10 9

8

Tour (5,4,5,3,2,3,1,3,5,6,5,8,9,8,10,8,7,11,7,8,5)