Matching di peso massimo

(1)

Matching

Definizione Dato un grafo non orientato G = (V, A), un

matching su tale grafo è un sottinsieme M ⊆ A dell’insieme di archi A tale che non ci sono in esso coppie di archi

adiacenti, ovvero con un nodo in comune.

(2)

Matching di peso massimo

Se associamo ad ogni arco e ∈ A un peso w_e > 0 possiamo associare un peso anche a un matching M pari alla somma dei pesi degli archi in M, cioè:

w(M ) = X

e∈M

w_e.

(3)

Matching di peso massimo

Se associamo ad ogni arco e ∈ A un peso w_e > 0 possiamo associare un peso anche a un matching M pari alla somma dei pesi degli archi in M, cioè:

w(M ) = X

e∈M

w_e.

Nel problema di matching pesato si vuole determinare tra tutti i possibili matching in un grafo quello di peso massimo, cioè si vuole risolvere il seguente problema:

max

M ⊆A è un matching^w^{(M ).}

(4)

Applicazioni

Questo problema modella tutte le applicazioni in cui

abbiamo membri di un insieme (rappresentati dai nodi del grafo) alcuni dei quali accoppiabili tra loro (i nodi collegati da archi). Ad ogni potenziale accoppiamento si associa un peso (o profitto) e si vuole individuare quali coppie formare (tenendo conto che un membro dell’insieme può far parte al massimo di una coppia) in modo da massimizzare il peso (o profitto) totale

(5)

Esempio

Grafo non orientato G = (V, A) con:

V = {a, b, c, d, e, f },

A = {(a, b); (a, f ); (b, c); (c, d); (c, e); (d, e); (e, f )}

e:

Arco (a, b) (a, f ) (b, c) (c, d) (c, e) (d, e) (e, f )

Peso 4 2 3 6 2 5 1

(6)

Esempio

V = {a, b, c, d, e, f },

e:

Peso 4 2 3 6 2 5 1

Esempi di matching:

M = {(a, b); (c, e)} w(M ) = 4 + 2 = 6

(7)

Esempio

V = {a, b, c, d, e, f },

e:

Peso 4 2 3 6 2 5 1

Esempi di matching:

M₁ = {(a, b); (c, e)} w(M₁) = 4 + 2 = 6

M = {(a, b); (c, d); (e, f )} w(M ) = 4 + 6 + 1 = 11

(8)

Matching di cardinalità massima

Caso particolare:

w_e = 1 ∀ e ∈ A.

In tal caso il peso di un matching coincide con la sua cardinalità | M | e si parla di problema di matching di cardinalità massima.

(9)

Modello matematico - variabili

Ad ogni arco e associamo una variabile binaria x_e definita nel modo seguente:

x_e =

( 0 se e non viene inserito nel matching 1 altrimenti

(10)

Modello matematico-vincoli

Per garantire che le variabili x_e con valore pari a 1 formino effettivamente un matching introduciamo dei vincoli.

(11)

Modello matematico-vincoli

Per avere un matching su ogni nodo del grafo deve incidere al massimo un arco del matching.

(12)

Modello matematico-vincoli

Indichiamo per ogni nodo i ∈ V il seguente insieme degli archi incidenti su di esso:

δ(i) = {e ∈ A : e incide su i}.

(13)

Modello matematico-vincoli

Indichiamo per ogni nodo i ∈ V il seguente insieme degli archi incidenti su di esso:

δ(i) = {e ∈ A : e incide su i}.

Se vogliamo che al massimo un nodo del matching incida su ogni nodo i del grafo, dovremo imporre i seguenti vincoli:

X x_e ≤ 1 ∀ i ∈ V.

(14)

Nell’esempio

Nodo a:

x_ab + x_af ≤ 1

(15)

Nell’esempio

Nodo a:

x_ab + x_af ≤ 1 Nodo b:

x_ab + x_bc ≤ 1

(16)

Nell’esempio

Nodo a:

x_ab + x_bc ≤ 1 Nodo c:

x_bc + x_cd + x_ce ≤ 1

(17)

Nell’esempio

Nodo a:

x_bc + x_cd + x_ce ≤ 1 Nodo d:

x_cd + x_de ≤ 1

(18)

Nell’esempio

Nodo a:

x_cd + x_de ≤ 1 Nodo e:

x_ce + x_de + x_ef ≤ 1

(19)

Nell’esempio

Nodo a:

x_cd + x_de ≤ 1 Nodo e:

x_ce + x_de + x_ef ≤ 1 Nodo f:

x_af + x_ef ≤ 1

(20)

Modello matematico - obiettivo

L’obiettivo del problema è il peso totale del matching che è dato dalla seguente espressione:

X

e∈A

w_ex_e.

(21)

Modello matematico - obiettivo

L’obiettivo del problema è il peso totale del matching che è dato dalla seguente espressione:

X

e∈A

w_ex_e.

Nell’esempio:

4x_ab + 2x_af + 3x_bc + 6x_cd + 2x_ce + 5x_de + x_ef

(22)

Modello matematico finale

max P

e∈A w_ex_e P

e∈δ(i) x_e ≤ 1 ∀ i ∈ V x_e ∈ {0, 1} ∀ e ∈ A

(23)

Nell’esempio

max 4x_ab + 2x_af + 3x_bc + 6x_cd + 2x_ce + 5x_de + x_ef x_ab + x_af ≤ 1

x_ab + x_bc ≤ 1 x_bc + x_cd + x_ce ≤ 1

x_cd + x_de ≤ 1 x_ce + x_de + x_ef ≤ 1

x_af + x_ef ≤ 1

x_ab, x_af, x_bc, x_cd, x_ce, x_de, x_ef ∈ {0, 1}

(24)

In forma matriciale

Siano:

x il vettore di ordine | A | le cui componenti sono le variabili x_e, e ∈ A;

(25)

In forma matriciale

Siano:

w il vettore di ordine | A | le cui componenti sono i pesi w_e, e ∈ A;

(26)

In forma matriciale

Siano:

C la matrice dei vincoli di ordine | V | × | A |: coincide con la matrice di incidenza nodo-arco del grafo;

(27)

In forma matriciale

Siano:

0 e ¹ rispettivamente il vettore le cui componenti sono tutte pari a 0 e quello le cui componenti sono tutte pari a 1;

(28)

In forma matriciale

Siano:

0 e ¹ rispettivamente il vettore le cui componenti sono tutte pari a 0 e quello le cui componenti sono tutte pari a 1;

I la matrice identica.

(29)

Modello in forma matriciale

max wx

Cx ≤ 1 Ix ≤ 1

x ≥ 0 intero dove:

wx ↔ P

e∈A w_ex_e;

(30)

Modello in forma matriciale

max wx

Cx ≤ 1 Ix ≤ 1

wx ↔ P

e∈A w_ex_e; Cx ≤ 1 ↔ P

e∈δ(i) x_e ≤ 1 ∀ i ∈ V ;

(31)

Modello in forma matriciale

max wx

Cx ≤ 1 Ix ≤ 1

wx ↔ P

e∈A w_ex_e; Cx ≤ 1 ↔ P

e∈δ(i) x_e ≤ 1 ∀ i ∈ V ;

Ix ≤ 1 e ^x ≥ 0 intero ↔ x_e ∈ {0, 1} ∀ e ∈ A

(32)

Nell’esempio

Vettore pesi ^w:

(4 2 3 6 2 5 1)

(33)

Nell’esempio

Vettore pesi ^w:

(4 2 3 6 2 5 1) Matrice ^C:

x_ab x_af x_bc x_cd x_ce x_de x_ef

a 1 1 0 0 0 0 0

b 1 0 1 0 0 0 0

c 0 0 1 1 1 0 0

d 0 0 0 1 0 1 0

e 0 0 0 0 1 1 1

f 0 1 0 0 0 0 1

(34)

Complessità

Il problema di matching appartiene alla classe P , ovvero esiste una procedura di complessità polinomiale che lo risolve.

(35)

Complessità

Nel caso di grafi bipartiti, dove ^C è TU, possiamo sfruttare il solito risultato sulle matrici TU.

(36)

Complessità

Nel caso di grafi bipartiti, dove ^C è TU, possiamo sfruttare il solito risultato sulle matrici TU.

Non possiamo invece in generale dimostrare questo utilizzando i risultati visti sulle matrici TU (per grafi non

orientati generici la matrice di incidenza nodo-arco ^C non è necessariamente TU).

(37)

Chiusura convessa

Per grafi generici i vincoli già introdotti non sono sufficienti per definire la chiusura convessa, occorre introdurre altri vincoli.

(38)

Chiusura convessa

Per grafi generici i vincoli già introdotti non sono sufficienti per definire la chiusura convessa, occorre introdurre altri vincoli.

Dato U ⊆ V , indichiamo con E(U ) l’insieme di tutti gli archi del grafo con entrambi gli estremi in U. I vincoli aggiuntivi sono i seguenti:

X

e∈E(U )

x_e ≤ | U | 2

∀ U ⊆ V, | U | dispari

(39)

Nell’esempio

U = {a, b, c} → x_ab + x_bc ≤ 1 U = {a, b, d} → x_ab ≤ 1 U = {a, b, e} → x_ab ≤ 1

U = {a, b, f } → x_ab + x_af ≤ 1 U = {a, c, d} → x_cd ≤ 1

U = {a, c, e} → x_ce ≤ 1 U = {a, c, f } → 0 ≤ 1 eccetera ...

(40)

Problema (P conv)

max P

e∈A w_ex_e P

e∈δ(i) x_e ≤ 1 ∀ i ∈ V P

e∈E(U ) x_e ≤ j

|U | 2

k ∀ U ⊆ V, | U | dispari x_e ≥ 0 ∀ e ∈ A

(41)

Nota bene

Il numero dei vincoli aggiuntivi è esponenziale rispetto alla dimensione del problema di matching.

(42)

Nota bene

Il numero dei vincoli aggiuntivi è esponenziale rispetto alla dimensione del problema di matching.

Tuttavia, il problema (P conv) è risolvibile in tempo polinomiale in quanto, dato un generico vettore

x ∈ R^|A|, x ≥ 0, è possibile stabilire in tempo polinomiale se questo soddisfa o meno i vincoli aggiuntivi.

(43)

Grafi bipartiti: cardinalità massima

In tutte le applicazioni in cui gli elementi accoppiabili tra loro appartengono a due classi distinte (ad esempio, lavoratori da una parte e lavori dall’altra), il grafo corrispondente

G = (V, A) è un grafo bipartito con le due classi di bipartizione V₁ e V₂.

(44)

Grafi bipartiti: cardinalità massima

In tutte le applicazioni in cui gli elementi accoppiabili tra loro appartengono a due classi distinte (ad esempio, lavoratori da una parte e lavori dall’altra), il grafo corrispondente

G = (V, A) è un grafo bipartito con le due classi di bipartizione V₁ e V₂.

Faremo inoltre l’ulteriore ipotesi che tutti i pesi siano uguali a 1 ovvero consideremo il problema di matching di

cardinalità massima su grafi bipartiti.

(45)

Un esempio

Grafo bipartito G = (V₁ ∪ V₂, A) con:

V₁ = {a₁, a₂, a₃, a₄} V₂ = {b₁, b₂, b₃, b₄}

A = {(a₁, b₁); (a₂, b₂); (a₂, b₃); (a₂, b₄); (a₃, b₂); (a₄, b₁)}

(46)

Un matching iniziale

Un matching di partenza (non necessariamente di

cardinalità massima) può essere ottenuto con la seguente semplice procedura:

(47)

Un matching iniziale

Un matching di partenza (non necessariamente di

cardinalità massima) può essere ottenuto con la seguente semplice procedura:

Inizializzazione Si ponga M = ∅.

1. Se esiste un arco e ∈ A \ M che non sia adiacente ad alcun arco in M, allora porre M = M ∪ {e} e ripetere il passo 1. Altrimenti: STOP.

(48)

Algoritmo di risoluzione

Inizializzazione Sia M un matching di partenza

(eventualmente individuato con la procedura vista).

(49)

Algoritmo di risoluzione

Passo 0 Tutti i vertici del grafo sono non etichettati.

(50)

Algoritmo di risoluzione

Passo 0 Tutti i vertici del grafo sono non etichettati.

Passo 1. Se non c’è alcun vertice del grafo in V₁ che soddisfa le seguenti proprietà

è non etichettato;

su di esso non incide alcun arco in M,

allora: STOP. Altrimenti si seleziona un vertice del grafo in V₁ con tali proprietà e gli si assegna etichetta (E, −). Si inizializzi l’insieme R dei vertici analizzati con R = ∅.

(51)

Passo 2. Se tutti i vertici etichettati sono stati analizzati, ritornare al Passo 1; altrimenti selezionare un vertice k etichettato ma non analizzato ed analizzarlo, cioè si ponga R = R ∪ {k}. Analizzare un vertice vuol dire compiere le seguenti operazioni:

(52)

Se la prima componente dell’etichetta di k è una E, allora si assegna un’etichetta (O, k) a tutti i vertici del grafo adiacenti a k e non ancora etichettati; quindi si ripete il Passo 2.

Se la prima componente dell’etichetta di k è una O, allora sono possibili due casi

(53)

Se la prima componente dell’etichetta di k è una E, allora si assegna un’etichetta (O, k) a tutti i vertici del grafo adiacenti a k e non ancora etichettati; quindi si ripete il Passo 2.

Se la prima componente dell’etichetta di k è una O, allora sono possibili due casi

Caso 1 C’è un arco marcato incidente su k: in tal caso si assegna l’etichetta (E, k) al vertice unito a k dall’arco in M e si ripete il Passo 2.;

Caso 2 Non ci sono archi in M incidenti su k. In tal

(54)

Continua

Passo 3. Utilizzando la seconda componente delle etichette risalire dal vertice k in cui ci si è bloccati al

Passo 2 fino al vertice s con seconda componente pari a −. In questo modo si è individuato un cammino da s a k che inizia con un arco non appartenente a M,

prosegue alternando archi in M e archi non

appartenenti a M, e termina in k con un arco non appartenente a M. A questo punto si aggiorna M

invertendo l’appartenenza e non appartenenza a M per i soli archi lungo tale cammino. Quindi, tutti gli archi non appartenenti a M lungo il cammino vengono inseriti in M e viceversa. Infine si cancellano tutte le etichette ripartendo dal Passo 1.

(55)

Complessità dell’algoritmo

Si può dimostrare che questo algoritmo richiede un numero di operazioni O(min(| V₁ |, | V₂ |) | A |) e ha quindi

complessità polinomiale.

(56)

Complessità dell’algoritmo

Si può dimostrare che questo algoritmo richiede un numero di operazioni O(min(| V₁ |, | V₂ |) | A |) e ha quindi

complessità polinomiale.

Va sottolineato che non è il meglio che si possa ottenere

per questo problema. Esiste infatti anche un altro algoritmo, che non vedremo, la cui complessità è pari a

O(| V |^1/2| A |).

(57)

Un’osservazione

Il problema di matching di cardinalità massima su grafi

bipartiti può essere visto come caso particolare di problema di flusso massimo. Come?