Modelli e algoritmi per il problema di assegnamento …agnetis/mannino.pdfAssegnamento di frequenze...
Transcript of Modelli e algoritmi per il problema di assegnamento …agnetis/mannino.pdfAssegnamento di frequenze...
Modelli e algoritmi per ilproblema di assegnamento di
frequenze
Carlo Mannino
Università di Roma “La Sapienza”
Siena, giugno 2002
Assegnamento di frequenze
Frequency Assignment Problem (FAP)
Problema: assegnare frequenze ditrasmissione a reti di trasmettitori
Schema della presentazione
• Descrizione del problema
• Formulazioni standard
• Formulazioni e algoritmi più recenti
Rilevanza
• TV e Radio Broadcasting
• Telefonia Cellulare (GSM e, parzialmente, UMTS)
• Collegamenti militari e civili di vario genere
Applicativa
Teorica
• Generalizza il problema di colorazione di grafi
• Generalizza il problema del max k-cut
• Generalizza il problema del TSP
Il problema• Trasmettitori
• Aree di servizio
• Aree di interferenza
Aree di servizio e d’interferenza non sovrapposte
Trasmettitori possono usare la stessa frequenza
Altrimenti
Frequenze diverse
L’interferenza e le frequenze
T2
T1
p
-40
-30
-20
-10
0
10
20
30
40
50
0 50 100 150 200 250 300 350 400
dB
kHz
T1 T2
),,,( 21 gfTTpInterferenza generata da T1 in T2 se f èassegnata a T1 e g a T2.
Multi-Frequency-Network (MFN)
1
2
111
2
3 3
4
4
•F={1,2,..,k} frequenze.
• Una frequenza per ogni area.
Obiettivo : Minimizzare k assicurando un servizio accettabile
Come si misura la qualità del segnale ?
1 2 k200 MHz
La banda viene suddivisa in intervalli uguali (le frequenze)
Valutazione della qualità del servizio• Le aree di servizio sono suddivise in testpoints
- I campi utili e interferenti da ogni trasmettitore vengono calcolati in ogni testpoint (field prediction)
- Controllando i campi ricevuti posso valutare il servizio
Predizione di campo
• Esistono modelli molto accurati di predizione
- Tengono conto della conformazione del terreno
- Fanno uso della teoria di Fresnel (Deygout, Epstein-Peterson)
- Coinvolgono l’interferenza troposferica (Racc. ITU-EBU, BBC)
Valutazione della qualità del segnale
- Calcola il rapporto Segnale/Rumore (S/N) in ogni testpoint (facendo uso dei modelli di predizione di campo)
Confronta il rapporto S/N ratio con le soglie (protection ratios) raccomdandate dagli organismi internazionati (ITU,EBU) e assegna a ogni testpoint un valore secondo la seguente scala
S/N > t4 Q4 - Q5 (Buono - Eccellente)t3 > S/N > t4 Q3 (Discreto)S/N < t3 Q2 - Q1 (Scarso, Pessimo)
Torniamo al problemaDati:
• Un insieme di trasmettitori con parametri elettromagnetici noti (Coordinate, diagramma d’antenna, Quota, etc.)
• Una descrizione accurata del terreno (Terrain data bank)
• Una certa porzione della banda di frequenze
TROVA:
L’assegnamento di frequenze ai trasmettitori che minimizza l’uso dello spettro e soddisfai requisiti di qualità.
• Una soglia di qualità (e.g. 80% dei testpoint a qualità > Q4)
Minimum Order FAP
Il modelloObiettivo:
• Trasformare i requisiti di qualità in vincoli trattabili per il Frequency Assignment Problem
• Rappresentazione classica: il grafo d’interferenza
• Un grafo G(V,E) i cui vertici rappresentano i trasmettitori mentregli archi “trasportano” l’informazione sui requisiti di qualità
Le due scelte principali
- Modelli di max k-cut generalizzato
- Modelli di colorazione generalizzata
Colorazione generalizzataIl costo cij associato a ciascun arco ij rappresenta la minima distanzafra la frequenza assegnata ad i e quella assegnata a j in modo daassicurare il soddisfacimento dei requisiti di qualità
La quantità cij può essere calcolata in modi diversi:
• Interferenza sito-sito
• Interferenza sito-testpoint
• Distanza inter-sito “honeycomb tiling”
fi fj
i j
| fi-fj | > cij
cij
} Field prediction
Calcolo della distanzakT
hT
Ipotesi:
In ogni testpoint il rapporto S/N è- Sh/ Nk (Th serve - Tk interferisce ) oppure- Sk/ Nh (Tk serve - Th interferisce ) e dipende dalla distanza in frequenza ∆f = fh - fk
kT and hT sono i soli trasmettitori attivi
L1hk (d)= # di testpoint con Sh/ Nk < t4 e Sk/ Nh < t4 se ∆f =d
(non serviti a qualità Q4 se ∆f =d)
L1hk(dhk ) < r% di testpoint chk è il più piccolo intero per cui
G = (V,E,c) grafo non orientato
Frequency Assignment (MO-FAP)
WANT: trova il più piccolo k tale che esiste un k-assignment
cij peso dell’arco (i,j)
FrequencyAssignment
EijcjfifkVf ij ∈∀≥−→ ,|)()(| },,,1{: Κ
OSS. Se cij = 1 per ogni ij ∈ E, FAP = Coloring
1
2
5
2a
c
b
1
4
1
26 span(f) = max f(v) - 1 v∈V
span(G) = minf span(f)
G = (V,E,c,d) grafo non orientato, con costi su archi e domande
Frequency Assignment con domanda
di domanda di frequenze del nodo i,
• In genere, la stessa antenna viene utilizzata pertrasmettere più programmi TV o servire più telefoni
WANT: trova F* di minimo span
• Frequency Assignment: famigliadi insiemi di frequenze Fi per ogninodo i ∈ V, con la proprietà che
g ∈ Fi e f ∈ Fj ⇒ |g-f| ≥ cij
icii
span(G,d) = span(F*)
Dato un assegnamento F
span(F) differenza fra la più piccola e la più grande frequenza assegnate
Aardal, Adjakplè, Al-Khaled, Battiti, Beall, Beckmann,Bertossi, Borndörfer, Bouju, Box, Boyce, Brunato,Caminada, Carbonaro, Carlsson, Castelino, Chang,Chardaire, Coghill, Costa, Crisan, Crompton, Cuppini,Del Re, Dimitropoulos, Dorne, Dowd, Duque-Anton,Eisenblätter, Fantacci, Fischetti, Funabiki, Galinier,Gamst, Grindal, Grötschel, Hao, Hellebrandt, Heller,Hurley, Jaimes-Romero, Johnston, Kapsalis, Ketchum,Kilakos, Killat, Kim, Knälmann, Kunz, Kolen, Koster,Janssen, Jansen, Jaumard, Lai, Laird, Leese, Li,Lochtie, Malesinska, Maniezzo, Martin, Mathar,Mattfeldt, McEliece, Minton, Montanari, Munoz-Rodriguez,Mühlenbein, Müller, Nasrabadi, Ngo, Palaniswami, Park,Perrier, Petford, Quellmalz, Rayward-Smith, Rodriguez-Tellez, Romanin-Jacur, Ronga, Roos, Rushforth, Rüber,Sandalidis, Sassano, Sivarajan, Smith, Stephens,Stavroulakis, Sung, Takefuji, Taylor, Tcha, Tekinay,Terlaky, Thiel, Toto, Tsang, Valenzuela, van de Heuvel,Van Hoesel, Vom Scheidt, Voudouris, Yum, Walser, Wang,Warners, Welsh, Wong, Zerovnik, Zhang, Zoellner
La letteratura è vastissima
∑f∈K xif = di per ogni i ∈ V
xif - xjg ≤ 1 per ogni ij ∈ E, g, f ∈ K, |g – f| < cij
Formulazione Classica
xif =1 se frequenza f è assegnata a nodo i
0 altrimenti OBS: |V| · k variabili
1. Inerferenza: due trasmettitori interferenti non possonoricevere frequenze vicine.
2. Domanda: ogni trasmettitore i riceve di frequenze.
VINCOLI
Variabile xif per ogni coppia nodo-frequenza
Funzione Obiettivo
• Per ogni problema viene modificato il valore di k
• Alternativa: trova k cui corrisponde una soluzione ammissibile eintroduci ulteriori variabili binarie
• In ogni caso, il numero di variabili binarie cresce al crescere dellospan di G
• L’obiettivo (minimizzazione delle frequenze) viene trasformato inun certo numero di problemi di ammissibilità
• Approccio standard: branch and cut.
Minimum Interference FAP
• Esistono molte versioni di FAP, con vincoli e funzioni obiettivo diversi.
• La principale variante: il numero di frequenze k è fissato
• In particolare, ad ogni arco del grafo d’interferenza associo uno opiù costi di violazione, che rappresentano il numero dei testpointviolati quando i due trasmettitori corrispondenti interferiscono.
p(r,s,g,f)
s
r
Problema: assegnare le frequenze {1,…,k} inmodo da minimizzare la somma dei costi diviolazione.
(FAP) Assegna a ogni nodo u di G una frequenza f(u) ∈{1,…,k}minimizzando il costo d’interferenza c(f)
c(f) = ∑u,v g(f(u), f(v))PROBLEMA: c(f) “complicata”
ove il costo d’interferenza a coppie g(f(u), f(v)) = g(|f(u)-f(v)|) dipende dalla distanza delle frequenze assegnate a u e v.
Problema di Clustering
Problema di clustering:
Dato un insieme di elementi V = {1,…,n}, associamo aogni k-partizione π di V un costo c(π).
Trova la partizione π che minimizza c(π).
V1
V2
V3
uπ(u) = V3
Clustering su grafi
Clustering su grafi Dato un grafo G = (V,E) e un costo ce per ogni e∈E
Max k-cut π = {V1,…, Vk}, c(π) = ∑q ∑ij cij , i∈Vq , j∈Vq
k-coloring Risolvi il problema di max k-cut. G è k-cromatico see solo se c(π) = 0.
V1
V2
V3
Se p(r,s,g,f) > 0 solo se g = f , allora MI-FAP siriduce al max k-cut problem.
Bound alternativi per MO-FAP
Th. [Raychauduri ’83]: il costo H(G) del camminohamiltoniano di costo minimo è un lower bound per span(G)
Span(G) = 41
2
5
A
C
B
1 2
4
c(P) = 3 < Span(G) = 4
Obiettivo: trovare formulazioni per MO-FAP chesvincolino il numero dell variabili dallo span del grafo
Consideriamo ora il camminohamiltoniano P = {A,C,B}
Perché?
Cammini hamiltoniani di costo minimoSia f l’assegnamento ottimo.
Ordina i nodi V = {1,..,n} in modo tale che f(1) ≤ f(2) ≤ … ≤ f(n).
Si ha, in generale f(i+1) - f(i) ≥ ci,i+1
)()(1
11,
1
111 GHcffffGspan
n
iiii
n
iin ≥≥−=−= ∑∑
−
=+
−
=+
e quindi
1 2 n-13 nc1,2 c2,3 cn-1,n )(
1
11, GHc
n
iii ≥∑
−
=+
f(2)-f(1) ≥ c1,2 f(3)-f(2) ≥ c2,3
Generalizzazione: d-walks
d-walk: cammino che passa per ogni nodo esattamente d volte
Span(G,d) = 4
AC BC1 1 2
Th. [Janssen, Kilakos 96]. Il costo di un d-walk dicosto minimo è un lower bound per span(G).
s
Aggiungo s percercare camminichiusi
2
1,3
5da = 1, db = 1, dc = 2
A
C
B
1 2
4
2
s
ds = 1
Σe∈δ(S) ye ≥ 1 per ogni S ⊂V
Formulazione del d-walk minimo
ye = # volte l’arco e è usato dal d-walk
1. Ogni nodo u appare du volte sul cammino
VINCOLIΣv≠ u yuv + 2yuu= 2du per ogni u
2. La soluzione è connessa:
Janssen e Kilakos 96
• La formulazione (JK) viene rilassata per calcolare bounds per FAP
Funzione Obiettivo min Σe∈E ce ye
• Domande unitarie: classica formulazione del TSP
• Il (multi) grafo indotto dalla soluzione è euleriano: ogni nodo hagrado pari. Quindi ammette un ciclo euleriano.
Costruire il d-walk
A
B
C
s ds= 1, dA= 2, dB= 3, dC= 2
ys,A + yA,B + yA,C + 2yA,A = 4ys,B + yA,B + yB,C + 2yB,B = 6ys,C + yA,C + yB,C + 2yC,C = 4ys,A + ys,B + ys,C = 2
�A,C = 3 �B,B = 2 �s,B = 1 �s,C = 1�A,B = 1
B
B B s
C
ACA
Formulazioni esatte
• Purtroppo in generale c’è un gap fra il valore ottimodella formulazione (JK) e la soluzione ottima di FAP
Th. [Avenali, Mannino, Sassano] Se c ∈ R|E| è una semimetrica(soddisfa cioè la disuguaglianza triangolare) allora laformulazione (JK) è esatta.
L’origine del gap
span(G) = 4A
C
B
1 2
41
2
5
H(G) = 3GAP = 4-3 = 1 OBS Grafo Semplice
sequenza di nodi cammino
Def. span(P) = costo della sottosequenza di costo massimo
• Oriento gli archi sul cammino da A a B• Oriento transitivamente gli altri archi
Def. span(P) = costo del cammino massimo da A a B
OBS: La sequenza P = {A, C, B} contiene una sottosequenza {a,b}di costo maggiore.
4
A C B1 2
Alternativamente
FAP versus Span
Th. [Avenali, Mannino, Sassano]. Il valore di un assegnamento difrequenze ottimo è pari allo span del d-walk di minimo span.
span(G,d) = minP span(P): P d-walk
FAP Trova il d-walk di minimo span
Obiettivo: costruire una formulazione di PLI per il problemadi trovare il d-walk di minimo span
Bad Walks
A B C2 2
5
D
2
3
1
Def. P è un bad walk se c(P) < span(P)
c({A,B,C,D}) = 5
c({A,C,D}) = 6
Co: se il d-walk di costo minimo P* non è bad, allora
c(P*)=span(P*)= span(G,d)
A B C3 5
3
D
3
4
2
Generare “good walks”OSS: Ogni d-walk è la concatenazione di archi.
OSS: Il costo di un d-walk è la somma dei costi degli archi
A B C2 2
5
D
2
3
2 E2
8
6
A B C
c({P}) = 8 span(P) = 11
w1
C D Ew2
OSS: se definisco 2 walk:
P = w1 ° w2
c(w1) = span(w1) = 5 c(w2) = span(w2) = 6
span(P) = c(w1) + c( w2)!
Concatenazioni bad• Costruisci un “serbatoio” di walk (anche con archi) W (base).
• A ogni w∈W associa un costo cw = span(w)
• Costruisci d-walk di minimo span concatenando elementi di W.
A B2 2
5
C
A B Cw1
c(w1) = span(w1) = 5
Proibisci la concatenzione (A,B) • (B,C)
Aggiungi w1 = (A,B) • (B,C)
Obiettivo: costruire concatenazioni di walks i cui costi (span)possono essere sommati per ottenere lo span della concatenazione
Def: w1•w2 • … • wq concatenazione bad se
span(w1•w2 • … • wq) > span(w1) + …+ span(wq)
Concatenazioni ammissibili
• Definisci la coppia (W,I):
W insieme di walk I ⊆ W×W coppie di walk incompatibili
Def. Concatenazione ammissibile (per (W,I))
w1, w2, …, wq∈ W:w1•w2 • … • wq
(wi,wi+1)∉I per i = 1,…, n-1
Def. (W,I) è completa se ogni walk di G è ammissibile
Def. (W,I) è good se ogni concatenazione ammissibile è non bad
Generare (W,I) completa e good
A B2 2
5
C
A B Cw1
1. Proibisci la concatenzione (A,B) • (B,C)
2. Aggiungi w1 = (A,B) • (B,C)
W = {(A,B),(B,C),(A,C), w1}
tutti gli archi
I = {((A,B),(B,C))}
c(w1) = span(w1) = 5c((A,B)) = span((A,B)) = 2c((B,C)) = 2 c((A,C)) = 5
(W,I) è completa! Es. Il walk {B,C,A,B,C} = (B,C) • (C,A) • w1
Inoltre span({B,C,A,B,C}) = c((B,C)) + c((C,A)) + c(w1) = 12
Che fare se i bad walks (minimali) contengono 3 o più archi?
Bad walks lunghi
A B Cw1
1. Aggiungi e proibisci
w1 = (A,B) • (B,C)
A B2 2
3
C D2
3
7
W = {(A,B), (A,C), (A,D), (B,C), (B,D), (C,D), w1} I = {((A,B),(B,C))}
2. Aggiungi e proibisci w2 = w1 • (C,D)
I = {((A,B),(B,C)),(w1,(C,D))}
c(w1) = span(w1) = 4
A B Cw2
D
W = {(A,B), (A,C), (A,D), (B,C), (B,D), (C,D), w1, w2}
c(w2) = span(w2) = 7
Equivalenza con FAP
Th. [Avenali, *, Sassano] Se (W,I) completa e good ⇒⇒Trovare d-walk ammissibile per (W,I) di costo minimo ⇔ FAP
Th. [Avenali, *, Sassano] Se per ogni (r,s) ∈ I, si ha r•s ∈ W⇒⇒ (W,I) completa
• Il metodo visto nella slide precedente assicura quindi la completezzadi (W,I)
• Se applicato ricorsivamente a ogni concatenzione bad ottengo (W,I)good.
Formulare il good d-walk
• Variabili yw = # volte il walk w ∈ W è usato dal d-walk
• Coefficienti aw(u) = # walk w passa per u
Data (W,I) completa e good possiamo costruire una formulazionedel problema di trovare un d-walk ammissibile di costo minimo.
Funzione Obiettivo min Σw∈W cw yw
• Ogni nodo u appare du volte sul cammino
Σw aw(u) yw = 2du per ogni u
Vincoli
Come assicurare che la soluzione sia
connessa
ammissibile per I
Un esempio
A B Cw1
A B2 2
6
C
I = {((A,B),(B,C))}W = {(A,B),(A,C), (B,C),w1 , (s,A), (s,B), (s,C)}
c(A,B) = 2 , c(B,C) = 2,c(A,C) = 6, c(w1) = 6
min 2yA,B + 2yA,B + 6yA,C + 2yB,C + 6yw1
dA = 2dB = 2dC = 1
s
ys,A + yA,B + yA,C + yw1 = 4ys,B + yA,B + yB,C + 2yw1 = 4ys,C + yA,C + yB,C + yw1 = 2ys,A + ys,B + ys,C = 2
�s,A = 2 �A,B = 2 �B,C = 2
A B C
s
Grafo delle transizioni
A B Cw1
A B2 2
6
C
I = {((A,B),(B,C))}
s
W = {(A,B),(A,C), (B,C),w1 , (s,A), (s,B), (s,C)}
Grafo T=(W,F)F = {(r,s): r,s∈W e r e s possono esser concatenati}
W è l’insieme dei walk
(r,s)∈Fr,s un estremo in comune
(r,s)∉I(A,B)
(A,C)(B,C)
w1
(s,A)
(s,B)
(s,C)
A che serve il grafo delle transizioni
Th. [Avenali, *, Sassano] Sia � tale che Σw aw(u) �w = 2du , per ogniu.Allora esiste un d-walk ammissibile per (W,I) costruitoconcatenando i walk di � se e solo se esiste un �-walk in T.
Un esempio
(A,B)
(A,C)(B,C)
w1
(s,A)
(s,B)
(s,C)
�s,A = 2 �A,B = 2 �B,C = 2
(A,B)(B,C)
(s,A)
2
2
2
Non esiste un � walk in T! s’ 1
La formulazione completa
Sia (W,I) completa e good. T = (W,A) grafo di transizione associato.
min Σw∈W cw yw
Σw aw(u) yw = 2du per ogni u
Σe∈δ(w) ze = 2 yw per ogni w ∈ W
yw = # volte il walk w ∈ W è usato dal d-walkze = # volte l’arco e ∈ A è usato dall’ y-walk
Σe∈δ(S) ze ≥ yw / M per ogni S ⊂W, con w∈W – S e s’∈S
L’algoritmo: generazione dinamica divariabili e vincoli
OSS. il numero di vincoli e variabili può essere moltoelevato.
• L’algoritmo costruisce una sequenza di coppie (Wk, Ik)complete con la proprietà che Wk ⊂ Wk+1 e Ik ⊂ Ik+1
OSS. Non occorre che (W,I) sia good.
• All’iterazione k risolve la formulazione associata a (Wk,Ik)
• Costruisco il d-walk P = {w1•w2 • … • wq} associato a �k
• Se P è non bad STOP. P è un d-walk di minimo span
• Altrimenti costruisci Wk+1 e Ik+1 e ricomincia.
Aggiornamento di (W,I)
P = {w1•w2 • … • wq} bad walk minimale generato.
• Poni Wk+1 = Wk ∪ {r1,r2, …, rq-1 }.
Sia r1 = w1•w2 , r2 = r1•w3, …, rq-1 = rq-2•wq
• Poni Ik+1 = Ik ∪ {(w1•w2), (r1•w3), …, (rq-2•wq) }.
N1 N2 N3 Nq-1 Nqw1 w2
r1
N4
w3
r2rq-1
Distanze e semimetriche
Distance Space (X,d)
Insieme X
Funzione distanza d: X × X→ R+
d(i,j) = d(j,i) ∀ i,j ∈ X
d(i,i) = 0 ∀ i ∈ X
Se: d semimetrica su X
(d metrica se d(i,j) = 0 → i = j)
d distanza definita su Vn → (simmetria) d ∈ R|En |
X = Vn = {1, …, n} En = {ij: i,j ∈ V, i ≠ j} ij insieme di coppienon ordinate
d(i,j) ≤ d(i,k) + d(j,k) ∀ i,j,k ∈ XI vincoli
definiscono un cono in R|En | detto cono semimetrico METn
d(i,j) ≤ d(i,k) + d(j,k) ∀ i,j,k ∈ X
Assegnamenti di frequenze e semimetriche
Istanza di FAP G = (V,E,c)1
42
32 3
2
1
0
1
1
53
2
241213
w =
1,21,31,42,32,43,4
f: V → N assegnamento ammissibile
Semimetricaw(i,j) = |f(i) – f(j)|
Dato un spazio con norma (E, ||.||):
d(x,y):= || x-y||, x,y ∈ E Minkoswski metricmetrica
Assegnamento di frequenze a V associo Semimetrica w su V, w ≥ c
Idea: trovo semimetrica w, con w ≥ c associo f: w(i,j) = |f(i) – f(j)|
Semimetriche e assegnamenti di frequenze
12
33
1
3
Purtroppo …
In questo caso non esiste f: V → N tale che w(i,j) = |f(i) – f(j)|
OSS: trovare semimetriche w su V, con w ≥ c è facile!
w(i,j) ≤ w(i,k) + w(j,k) ∀ i,j,k ∈V
w(i,j) ≥ cij ∀ i,j,∈V Vincoli lineari!
w = c
Def. Sia w semimetrica. Se esistono n numeri reali {f1, …, fn} tali chewij = |fi – fj| for i,j ∈ {1,…, n} allora w è detta embeddable nellospazio metrico (R, dl1) (l1 è la norma 1).
embeddable11l
Riassumendo
Trovare un assegnamento ammissibile equivale a trovare w ∈ R|E| tale che
2. w ≥ c
1. w è una semimetrica
Problema: quando w ∈ METn è l11 embeddable?
embeddable11l3. w is
Tagli!
δ(S) ∈ {0,1}|E| vettore d’incidenza del taglio (S:V-S)
} allfor 0|)({CUTn VSS SVS
S ⊆≥= ∑⊆
λδλ Cut cone
Si definisce Cut cone
1
42
3
S
Dato un grafo G = (V,E), sia S ⊂ V.
Chiamamo taglio (S:V-S) l’insieme degliarchi con un estremo in S e l’altro in V-S
Es. S = {1}
Es. (S:V-S) = {(1,2), (1,3), (1,4)}111000
1,21,31,42,32,43,4
δ(S) =
Semimetriche su V embeddabili nello spazio l11
Torniamo alla domanda: quando w ∈ METn è l11 embeddable?
1. w ∈ CUTn
w = λ1 δ(S1) + λ2 δ(S2) + … + λq δ(Sq)
S1, S2 , … , Sq ⊂ V, λ1 , λ2 , …, λq ≥ 0
2. S1, S2 , … , Sq nested family S1 ⊂ S2 ⊂ … ⊂ Sq
1352
f =1234
1
42
32 3
2
1
0
1
241213
w =
1,21,31,42,32,43,4
S1= {1}
S1
1
42
32 3
2
1
0
1
S2
⊆ S2= {1,4} ⊆ S3= {1,4,2}
1
42
32 3
2
1
0
1
S3
111000
1,21,31,42,32,43,4
δ(S1) =
231201
c =
1,21,31,42,32,43,4
110011
1,21,31,42,32,43,4
δ(S2) =
010101
1,21,31,42,32,43,4
δ(S3) =
111000
1·
110011
+ 1·
010101
+ 2 ·
241213
= = w
1
53
2
w(i,j) = |f(i) – f(j)|
Formulazione: variabili di decisione
C insieme di tutti i tagli di G
Ovvero: trova semimetrica w ≥ c, tale che w sia l11 embeddable.
l11 embeddable: trova una nested family di tagli tale che w possa
esprimersi come combinazione conica dei tagli della famiglia
yC =1 se C ∈ C appartiene alla nested family
0 altrimenti
λC ≥ 0 moltiplicatore per C ∈ C nella combinazione conica
z ≥ 0 valore della massima componente di w
FAP: trova f tale che sia minimo maxi,j ∈ V |f(i) – f(j)|
Vincoli I
Vincolo 1: per ogni arco, we ≥ ce
we =
C e = {C ∈ C : e ∈ C}
∑ λC ≥ ceC∈C e
e ∈ E
Vincolo 2: z è (più grande della) la più grande componente di w.
z ≥ ∑ λCC∈C e
for all e ∈ E
insieme di tutti i tagli che contengono l’arco e
Vincoli II
Vincolo 3: λC è 0 se C non è scelto.
λC - M·yC ≤ 0 per ogni C ∈ C
M può essere scelto come max ce , e ∈ C
Vincolo 4: y è il vettore d’incidenza di una nested family
Th [Deza, Laurent]: una famiglia di tagli B è nested se e solo se perogni X ⊆ B con | X | ≤ 3, X è nested.
yi + yj ≤ 1 per ogni non nested i, j ∈ C
yi + yj + yk ≤ 1 per ogni non-nested i, j, k ∈ C
La formulazione
yi + yj ≤ 1 per ogni non-nested i, j ∈ C
yi + yj + yk ≤ 2 per ogni non-nested i, j, k ∈ C
we = ∑ λC ≥ ceC∈C e
per ogni e ∈ E
z ≥ ∑ λCC∈C e
per ogni e ∈ E
λC - M·yC ≤ 0 per ogni C ∈ C
min z
Risolvere il rilassamento
costo ridotto:
• La formulazione può essere usata all’interno di un algoritmo dibranch-and-bound
• Column generation: • Risolvi all’ottimo il rilassamento con un sottoinsieme di variabili • Se tutte le variabili hanno costo ridotto positivo o nullo: STOP. • Aggiungi una colonne con costo ridotto negativo • Torna a 1.
• Tuttavia il numero di vincoli e di variabili è troppo grande perpoter essere risolto esplicitamente
• Approccio standard: generare variabili e vincoli quando servono.
Variabili dualiCome generare colonne per il nostro problema?
yi + yj ≤ 1 non-nested i, j ∈ C ’
yi + yj + yk ≤ 2 non-nested i, j, k ∈ C ’
-∑ λC ≤ -deC∈C e
e ∈ E
∑ λC - z ≤ 0C∈C e
e ∈ E
λC - M·yC ≤ 0 C ∈ C ’
OSS. Le colonne sono associate con tagli
C ’ insieme di tagli (colonne) contenuti nel nostro rilassamento
Variabili duali
πe
ϕe
Coefficienti nulli perλC e yC per C ∈ C -C ’
Column generation
OSS. Vogliamo trovare una colonna che minimizza il costo ridotto
Costo ridotto di λC ∑ ϕe -∑ πee ∈ C e ∈ C
1. Trovi il taglio di massimo peso in G, ove i pesi del taglio sonodati da πe - ϕe, for e ∈ E
2. Se il taglio ha peso positivo aggiungilo a C ’.
3. Aggiungi i vincoli associati alla nuova variabile.