Progetto di reti

Facility Location Game

Il gioco considerato è un problema di cost sharing. L’idea è quella di suddividere il cost di un servizio tra vari giocatori in modo fair. Nel facility location un insieme N di clienti deve accedere a un certo servizio. Il servizio può essere erogato in diverse facility ed F è l’insieme di tutte le facility.

L’erogazione del servizio ha i seguenti costi:

• ciascun cliente j ∈ N può servirsi presso un centro i ∈ F che sia aperto, con un costo pari a d_ij;
• per ogni centro i ∈ F il costo di apertura è f_i;

La decisione da prendere è dunque quale facility aprire. Tale situazione è formulabile come un problema di programmazione lineare intera. Le variabili del problema sono:

• y_i, pari a 1 se la facility i è aperta e pari a 0 altrimenti;
• x_ij, pari a 1 se il cliente j si serve presso la facility i e pari a 0 altrimenti.

Il problema è dunque

min     ( ∑_i∈F f_i y_i + ∑_i∈F ∑_j∈N d_ij x_ij )     questa è la funzione di costo

∑_i∈F x_ij ≥ 1     j∈N     ogni cliente j deve servire     presso una sola facility

x_ij ≤ y_i    i∈F, j∈N     se un cliente j si serve     presso una facility, essa     deve essere aperta

x_ij, y_i ∈ {0,1}     i ∈ F, j ∈ N

Una soluzione ottima, indicato con v (N), deve avere una corrispondenza fisica, poiché l'algebra può fornire risultati non realizzabili. Figuriamoci, come delle facility aperte solo in parte. Si osservi come in una soluzione ottima il vincolo _∑i∈F x_i,j ≥ 1 sara soddisfatto all’uguaglianza.

Tuttavia, scrivere il vincolo con la disuguaglianza permette di associare al vincolo una variabile duale vincolata in segno.

Si supponga di aver risolto in modo esatto il precedente problema, ovvero di aver trovato una soluzione ottima per il problema di PL1. Ora si vuole ripartire tra gli utenti di N il costo della grande coalizione, soddisfacendo la razionalità collettiva. È dunque noto v (N). Per trovare il valore v (S) di una coalizione S⊂N si deve risolvere

min (_∑i∈F f_iy_i + _{∑i∈F ∑j∈S} d_i,j x_i,j)

_∑i∈F x_i,j ≥ 1

j∈S

x_i,j ≤ y_i; i∈F, j∈S

x_i,j, y_i∈ {0,1} i∈F, j∈S

In questa situazione si deve verificare che la funzione di costo sia subadditiva, poiché la funzione è appunto di costo e non di utilità. Nel seguito si sfrutta la seguente osservazione:

Nel caso del facility location, y^* è sempre almeno 1_,3.

y^* si può individuare tramite il seguente problema di programmazione lineare:

y^* = max ₁/_c(N)   ∑_{j ∈ N} d_j

∑_{j ∈ S} d_j ≤ c(S)   ∀S ⊆ N

ottenuto del rilassamento lineare del problema di PL;

W_D^*: la soluzione ottima del problema duale a quello ottenuto dal rilassamento lineare.

Allora z_I^* = z_RL^* = W_D^*. La distanza tra z_I^* e z_RL^* è detta gap d’interesse.

Si osservi che z_I corrisponde al costo della grande coalizione.

Qualunque soluzione del rilassamento lineare è maggiore o uguale dell’ottimo, e qualunque soluzione del duale è minore o uguale dell’ottimo del duale.

Il gap d’interesse corrisponde allo spazio di soluzioni “aggiunto” rilassando linearmente il problema.

Il valore di B_i,j è scelto come

B_i,j = max {0, d_j - d^_j}

per soddisfare i vincoli

B_i,j ≥ 0

l_j ≤ B_i,j + d_j

Se tuttavia non è soddisfatto il vincolo

∑_{j ∈ N} B_i,j ≤ f_j

è necessario scegliere le d_j diversamente.

Facility Location Game

Si ricorda che per calcolare y* occorre risolvere il seguente problema di programmazione lineare:

γ* c(N) = max _j∈N ∑ a_j

∑ _j∈S a_j ≤ c(S) ∀ S ⊂ N

L’obiettivo è mostrare che questo problema è il problema duale del rilassamento lineare

w(D) = max _j∈N ∑ α_j

∑ _j∈N β_i,j ≤ f_i, i ∈ F

d_j ≤ β_i,j + d_i,j i ∈ F, j ∈ N

α_j ≥ 0 j ∈ N

β_i,j ≥ 0 i ∈ F, j ∈

sono lo stesso problema. Per verificarlo, si deve mostrare che ogni soluzione stabile per il primo problema deve essere ammissibile per il secondo e viceversa.

Sia (d, β) una soluzione ammissibile per il duale. Si vuole dimostrare che essa è stabile, ovvero ∀ S ⊂ N ∑ _j∈S a_j ≤ c(S)

Si considera la soluzione ottima per il problema di facility location su S, che ha costo c(S) e aprirà un certo numero K di impianti e

soluzione ottima del duale è

d_A = 3.5d_B = 2.5d_C = 1.5β_1A = 1.5β_1B = 0.5β_2C = 0.5β_3A = 2.5β_2B = 1.5β_3C = 0.5

la soluzione ottima del primale è

y₁ = y₂ = y₃ = 1/2x_1A = x_3A = 1/2x_1B = x_2B = 1/2x_2C = x_3C = 1/2

Alla prima iterazione si sceglie il cliente che offre complessivamente di meno, dunque C. Le facility interessanti per C sono la seconda e la terza. Si apre la facility 2 poiché ha costo minore. Alla seconda facility si connettono tutti i clienti che hanno una facility interessante in comune con j. Dalla soluzione del primale:N_A = {1,3}N_B = {1,2}N_J = N_C = {2,3}e dunque N_A ∩ N_C = {3}, N_B ∩ N_C = {2}. Dunque A, B e C possono essere collegati alla facility 2.

Tutti i clienti.

Analisi del secondo algoritmo

Per l'algoritmo randomizzato, si vedrà come:

1. (Costo (atteso) di apertura delle facility) ≤ ∑_i∈F f_i . y_x
2. (Costo (atteso) di connessione delle facility al generico j) ≤ 2 ∑_j∈N λ_j^* + ∑_j∈C ∑_i∈F d_ij . x_ij^*

somma su tutti i clienti del costo di connessione Dj sul problema primale

da cui:

Costo (atteso) della soluzione dall'algoritmo ≤ 2OPT (D) + OPT (P)

Per il risultato 1) si considera la generica iterazione dell’algoritmo, nella quale si e' scelto il cliente j.

Il costo atteso per l’apertura delle facility gradite a j secondo la probabilità x_j^* e' ∑_i∈Nj f_i x_j^*.

Allora ∑_i∈Nj f_i . x_j^* ≤ ∑_i∈Nj f_i. y_i^*

da cui il procedimento e' analogo a quello visto per l’algoritmo deterministico.

Per il risultato 2), si considera la situazione raffigurata: