A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 A 11 A 12

Problema del Set Covering (PLI)

Una societ`a deve decidere sulla costruzione di alcuni nuovi impianti per la depurazione di acque in un distretto di 5 citt`a C i , i ∈ 1 . . . 5. Ha a disposizione 12 aree A i , i ∈ 1 . . . 12, ognuna delle quali pu`o servire una o pi` u citt`a secondo la seguente tabella (un “*” indica che la citt`a `e servita dal relativo impianto), che indica in penultima riga anche il costo (in MEuro) di installazione di ogni impianto e la capacit`a di depurazione (in 10 ⁹ kg/anno):

A ₁ A ₂ A ₃ A ₄ A ₅ A ₆ A ₇ A ₈ A ₉ A ₁₀ A ₁₁ A ₁₂

C ₁ * * * * * *

C ₂ * * * * * *

C ₃ * * * * *

C ₄ * * * * * *

C ₅ * * * * * * *

Costo 7 9 12 3 4 4 5 11 8 6 7 16

Capacit`a 15 39 26 31 34 24 51 19 18 36 41 34

Determinare, mediante un modello di Programmazione Lineare Intera, quali impianti vanno costruiti in modo tale che ogni citt`a sia servita da almeno un impianto, che il costo di costruzione sia minimo e che vengano depurati almeno 120·10 ⁹ kg/anno.

Proporre un’euristica di tipo greedy efficiente per il problema proposto (Set Covering

con vincoli di capacit`a).

Soluzione

Formulazione.

• Indici:

– sia i un indice sull’insieme delle aree (i ≤ m, dove m `e il numero delle aree, m = 12);

– sia j un indice sull’insieme delle citt`a (j ≤ n, dove n `e il numero delle citt`a, n = 5).

• Parametri:

– sia t ij = 1 se la citt`a j `e servita dall’impianto i e 0 altrimenti (come da tabella nel testo del problema);

– sia c i il costo di installazione di un impianto sull’area i;

– sia C i la capacit`a di depurazione di un impianto costruito sull’area i;

– sia Q la quantit`a minima di acqua da depurare (Q = 120).

• Variabili: sia x i = 1 se un impianto viene costruito sull’area i e 0 altrimenti (x i ∈ {0, 1}).

• Funzione obiettivo:

min X m

i=1

c _i x _i

• Vincoli:

– (ogni citt`a servita da almeno un impianto) per ogni j ≤ n: P m

i=1 t _ij x _i ≥ 1;

– (depurazione minima): P m

i=1 C _i x _i ≥ Q.

File modello in AMPL

# impianti di depurazione param m >= 0;

param n >= 0;

set M := 1..m;

set N := 1..n;

param costo{M} >= 0;

param t{M,N} binary;

param capacita{M} >= 0;

param depurazione_minima >= 0;

var x{M} binary;

minimize costo_totale: sum{i in M} costo[i] * x[i];

subject to covering{j in N}: sum{i in M} t[i,j] * x[i] >= 1;

subject to depurazione: sum{i in M} capacita[i] * x[i] >= depurazione_minima;

File dati in AMPL

# depuratori param m := 12;

param n := 5;

param costo :=

1 7

2 9

3 12

4 3

5 4

6 4

7 5

8 11

9 8

10 6

11 7

12 16 ;

param t: 1 2 3 4 5 :=

1 1 0 1 0 0 2 0 1 1 1 0 3 1 1 0 0 0 4 0 0 0 1 1 5 1 0 0 0 1 6 0 1 1 0 1 7 1 0 1 1 0 8 1 0 0 1 0 9 0 1 0 0 1 10 0 0 1 1 1 11 0 1 0 0 1 12 0 1 0 1 1 ; param capacita :=

1 15

2 39

3 26

4 31

5 34

6 24

7 51

8 19

9 18

10 36

11 41

12 34 ;

Soluzione AMPL/CPLEX

CPLEX 8.1.0: optimal integer solution; objective 15 3 MIP simplex iterations

0 branch-and-bound nodes costo_totale = 15.0000 x [*] :=

1 0.0000 2 0.0000 3 0.0000 4 1.0000 5 0.0000 6 0.0000 7 1.0000 8 0.0000 9 0.0000 10 0.0000 11 1.0000 12 0.0000

;

Euristica greedy

Supponendo di aver gi`a selezionato un insieme A di aree che servono un’insieme B di citt`a, per ogni i ∈ M \A sia

D _i = X

j∈N \B

t _ij (1)

il numero di citt`a scoperte che l’impianto i coprirebbe

Il costo marginale unitario di ciascun impianto, dato da d i = _D ^c

i

`e un costo “pesato”

dall’utilit`a effettiva dell’impianto. Si pu`o quindi proporre un’euristica greedy come segue:

1. Inizializza l’insieme delle citt`a servite B e l’insieme di aree selezionate A all’insieme

vuoto.

2. Ripeti i comandi seguenti fintantoch´e |B| < n o la capacit`a di depurazione delle aree selezionate A `e minore di Q, cio`e fintantoch´e almeno un vincoli non `e soddisfatto:

(a) per ogni i ∈ M \A si calcoli D i come in Eq. (1), e d i = _D ^c

i

; (b) si scelga la citt`a k = arg min{d i | i ∈ M \A};

(c) si aggiorni A ← A ∪ {k}, B ← B ∪ {j | t kj = 1}

L’implementazione proposta dell’euristica `e come segue:

model setcovering.mod;

data setcovering.dat;

print "Euristica GREEDY";

## dichiarazioni

# numero di citta‘ scoperte all’iterazione corrente param D >= 0;

# costo marginale unitario all’iterazione corrente param d >= 0;

# costo marginale unitario minimo param dmin >= 0;

# indice dell’area con costo marginale unitario minimo param k >= 0, integer;

# costo della soluzione euristica param hcost >= 0;

# aree selezionate nella soluzione euristica (A[area] = 1 se selezionata) param A{M} >= 0, binary;

# citta‘ coperte nella soluzione euristica (B[citta] = 1 se coperta) param B{N} >= 0, binary;

# cardinalita‘ dell’insieme delle citta‘ coperte param cardB >= 0;

# capacita‘ di depurazione delle aree selezionate param depuraz >= 0;

## inizializzazione valori let hcost := 0;

let cardB := 0;

let {i in M} A[i] := 0;

let {j in N} B[j] := 0;

let depuraz := 0;

## euristica

# ciclo esterno: continua l’euristica fino a che i vincoli sono soddisfatti repeat while(depuraz < depurazione_minima or cardB < n) {

let dmin := 1000000;

# ciclo interno: cerca l’area di costo marginale unitario minimo for {i in M : A[i] = 0} {

# aggiungi 0.001 affinche’ la divisione seguente non sia costo / 0 let D := sum{j in N : B[j] = 0} t[i,j] + 0.001;

let d := costo[i] / D;

if (d < dmin) then {

# se l’area i e‘ migliore delle precedenti, aggiorna let dmin := d;

let k := i;

} }

# al termine del ciclo interno abbiamo l’area migliore k

# aggiorna l’insieme delle aree selezionate let A[k] := 1;

# aggiorna il costo totale let hcost := hcost + costo[k];

# aggiorna la capacita‘ di depurazione let depuraz := depuraz + capacita[k];

# aggiorna l’insieme delle citta‘ servite for {j in N : t[k,j] = 1 and B[j] = 0} {

let B[j] := 1;

let cardB := cardB + 1;

} }

## stampa soluzione

print "euristica: costo = ", hcost;

print "euristica: soluzione = ";

for{i in M : A[i] = 1} { print i;

}

e la soluzione ottenuta `e:

Euristica GREEDY

euristica: costo = 16 euristica: soluzione = 4

5 6 7

Si osservi che la soluzione euristica `e peggiore di quella ottimale (costo 16 contro costo

15) ma non di molto (meno del 7% di differenza).