Localizzazione e copertura
Classe: BIP / MILP · Script: uno script e un notebook per problema
(python/fam08_1_capacitata.py … fam08_4_hub.py).
Prerequisiti
-
Da questo modulo, Capitolo 6 «Legami fra variabili»: attivazione aggregata e disaggregata, variabile di massimo, se e solo se.
-
Da questo modulo, Capitolo 7 «Assegnamento e scheduling»: i problemi 7.4 e 7.5, di cui qui si riusano i legami.
Obiettivi
Alla fine di questo capitolo sarai in grado di:
-
modellare l'apertura di una struttura e le variabili che ne dipendono;
-
scegliere fra attivazione aggregata e disaggregata e motivare la scelta;
-
aggiungere un budget sul numero di sedi aperte;
-
costruire a mano il bound primale e il bound duale di un problema di localizzazione.
Quattro problemi in cui si decide dove aprire una struttura — una sede, un hub — e come questo vincola le variabili che dipendono da quella decisione: dove spedire la merce, quali clienti servire, quali clienti coprire, a quale hub connettere ciascun terminale. Cambia, di problema in problema, la natura del legame fra la variabile di apertura e le variabili che ne dipendono e il modo in cui il budget sulle aperture entra nel modello.
I legami fra variabili che si rivedono qui
Attivazione aggregata (8.1): un'unica famiglia di vincoli fa da legame e da vincolo di capacità insieme, \(\sum_c y_{lc} \le u_l x_l\). Attivazione disaggregata (8.2): \(x_l \ge y_{lc}\), dedotta dalla CNF di un'implicazione booleana come nel problema 7.5, con un budget \(k\) sul numero di sedi. Se e solo se (8.3): un verso imposto da due famiglie di vincoli (soglia di segnale e interferenza), l'altro che segue dall'obiettivo. Attivazione aggregata e variabile di massimo (8.4): la stessa attivazione dell'8.1 insieme al legame di massimo \(z_j \ge c_{ij} x_{ij}\) già visto nel problema 7.4.
Notazione della famiglia
| Simbolo | Tipo | Significato |
|---|---|---|
| \(m\) | \(\in \mathbb{Z}_{\ge 1}\) | numero di sedi/hub candidati, \(l \in \{1, 2, \dots, m\}\) |
| \(n\) | \(\in \mathbb{Z}_{\ge 1}\) | numero di clienti/terminali, \(c \in \{1, 2, \dots, n\}\) |
| \(t_{lc}\) | \(\in \mathbb{Q}_{>0}\) | costo di trasporto/connessione dalla sede/hub \(l\) al cliente/terminale \(c\) |
| \(i_l,\ f_l\) | \(\in \mathbb{Q}_{\ge 0}\) | costo di apertura/attivazione della sede/hub \(l\) |
| \(u_l\) | \(\in \mathbb{Q}_{>0}\) | capacità della sede \(l\) |
| \(d_c\) | \(\in \mathbb{Q}_{>0}\) | domanda del cliente \(c\) |
| \(k\) | \(\in \mathbb{Z}_{\ge 1}\) | numero massimo di sedi aperte / capacità di ciascun hub |
| \(s_{lc}\) | \(\in \mathbb{Q}_{\ge 0}\) | intensità del segnale dalla sede \(l\) al cliente \(c\) |
| \(p_c\) | \(\in \mathbb{Q}_{>0}\) | profitto se il cliente \(c\) è coperto |
| \(t,\ b\) | \(\in \mathbb{Q}_{>0}\) | soglia di segnale e limite di interferenza |
I quattro problemi
-
8.1 Localizzazione capacitata
Dove aprire le sedi e quanto spedire da ciascuna: il vincolo di capacità è anche il legame di attivazione. Costo minimo.
-
8.2 p-mediana
Al più \(k\) sedi aperte, ogni cliente al più vicino aperto: attivazione disaggregata, dedotta dalla CNF.
-
8.3 Copertura con interferenza
Un cliente è coperto se e solo se riceve segnale sufficiente e non troppa interferenza: un problema di massimo con due vincoli di link.
-
8.4 Hub con costo massimo
Attivazione degli hub più il costo di connessione più alto per hub: la stessa variabile di massimo del problema 7.4, euristica riusata dal bin packing.
In sintesi
In sintesi
-
Nei quattro problemi si decide dove aprire una struttura e come questo vincola spedizioni, clienti serviti, copertura e connessioni.
-
L'attivazione aggregata fa da legame e da capacità insieme; quella disaggregata dà un rilassamento più forte.
-
Il se e solo se del problema di copertura ha un verso imposto dai vincoli e uno dall'obiettivo.
-
Il budget sulle aperture entra nel modello come vincolo di cardinalità sulle variabili delle sedi.