Dieta: vincoli di esclusione

Consideriamo un vincolo di esclusione del tipo: una dieta equilibrata comprende pasta o riso, ma non entrambi. Se le variabili $x_{pasta}$ e $x_{riso}$ fossero di tipo logico, imporre questo vincolo sarebbe analogo a quanto fatto sopra, ma purtroppo si tratta di variabili continue che rappresentano una quantità. Dobbiamo introdurre due variabili logiche $y_{pasta}$ e $y_{riso}$ che devono assumere il seguente significato:

$$y_{pasta} = \left\{ \begin{array}{ll} 1 & \mbox{se $x_{pasta} > 0$} \\ 0 & \mbox{altrimenti} \end{array} \right.$$

$$y_{pasta} = \left\{ \begin{array}{ll} 1 & \mbox{se $x_{riso} > 0$} \\ 0 & \mbox{altrimenti} \end{array} \right.$$

Per indurre le variabili $y_{pasta}$ e $y_{riso}$ ad assumere il significato di cui sopra, dobbiamo introdurre degli opportuni vincoli che le leghino effettivamente al valore di $x_{pasta}$ e $x_{riso}$. Supponendo che in qualsiasi soluzione ammissibile $x_{pasta}$ e $x_{riso}$ possano valere al massimo $M_{pasta}$ e $M_{riso}$ i vincoli che mettono in relazione le variabili $x$ e $y$ sono:

$$x_{pasta} \leq M_{pasta} y_{pasta}$$

$$x_{riso} \leq M_{riso} y_{riso}$$

$$y_{pasta}, y_{riso} \in \{0,1\}$$

in tal modo se $x_{pasta}$ o $x_{riso}$ assumono valore maggiore strettamente di 0, le corrispondenti variabili logiche $y$ devono valere 1 e il vincolo di esclusione è:

$$y_{pasta} + y_{riso} \leq 1.$$

Possiamo osservare che $y_{pasta}$ e $y_{riso}$ non sono obbligate ad assumere valore 0 se la corrispondente variabile $x$ vale 0. Dovremo quindi tener presente questo fatto nella formulazione completa del problema in modo da evitare che simili soluzioni possano inficiare la validità del modello.

I vincoli di esclusione sono un caso particolare di vincolo logico (or esclusivo). Vediamone altri come per esempio le implicazioni: se la variabile $x_1$ vale 1, allora deve valere 1 anche la variabile $x_2$; vedendo le variabili in accordo al loro significato logico il vincolo rappresenta l'implicazione $x_1\Rightarrow x_2$. Ricordando il significato dell'implicazione, tra tutte le configurazioni di valori delle variabili quello che dobbiamo vietare è $x_1=1, x_2=0$, che viene tradotto in termini matematici come:

$$x_1 \leq x_2.$$

Anche la negazione è facilmente traducibile in termini matematici utilizzando il complemento a 1, come abbiamo visto parlando delle variabili. Quindi ad esempio l'implicazione $x_1\Rightarrow x_2$ viene tradotta come:

$$x_1 \leq (1-x_2)$$

e quindi

$$x_1 + x_2 \leq 1.$$

Se vogliamo generalizzare le implicazioni al caso di più variabili, consideriamo $n+1$ variabili $x_1, x_2,\ldots,x_n$ e $y$, e il vincolo: ``se almeno $m$ variabili tra $x_1, x_2,\ldots,x_n$ valgono 1 allora $y$ deve valere 1". La sua traduzione in termini matematici è:

$$y \geq \frac{x_1 + x_2 +\ldots + x_n - m + 1}{n - m + 1}.$$

Osserviamo infatti che l'unico modo di avere una quantità maggiore di zero a destra del $\geq$ è fissare il valore di almeno $m$ variabili $x$ a 1. La quantità al denominatore serve a non superare mai il valore 1.i

Fino ad ora abbiamo visto esempi di problemi in cui la regione ammissibile è descritta da un poliedro convesso, o è data dai punti interi racchiusi in un poliedro convesso. Potrebbero verificarsi casi in cui tale proprietà viene meno e la regione ammissibile è data da un poliedro non convesso. Consideriamo ad esempio la regione ammissibile descritta in figura 2.

fig. 2 esempio di regione ammissibile non convessa

La regione in figura può essere descritta come unione di due poliedri convessi $P$ e $R$, come evidenziato dalla figura 3.

fig. 3: decomposizione del poliedro

Il poliedro $P$ è dato da $P=\{x\in \mathbb{R}^2: x_1 - x_2 \leq 0, x_2\leq 1, x_1\geq 0, x_2\geq0\}$, mentre $Q=\{x\in \mathbb{R}^2: x_1 + x_2 \leq 1, x_1\geq0, x_2\geq0\}$. Per fare l'intersezione dei due poliedri sappiamo che basta che tutti i vincoli di $P$ e di $Q$ valgano contemporaneamente, se invece ci interessa l'unione dobbiamo imporre che almeno uno dei due gruppi di vincoli valga. In primo luogo osserviamo che alcuni vincoli sono comuni ai due poliedri, in particolare $\{x_2\leq 1, x_1\geq 0, x_2\geq0\}$, quindi di fatto di questi vincoli possiamo anche fare l'intersezione, mentre quelli che caratterizzano più propriamente le due regioni ammissibili sono $x_1 - x_2 \leq 0$ per quel che riguarda $P$ e $x_1 + x_2 \leq 1$ per quel che riguarda $Q$. Dobbiamo fare in modo che nella nostra formulazione almeno uno di questi due vincoli valga, quindi, considerando il problema dal punto di vista opposto, questo significa che al massimo uno di questi due vincoli può venire reso ridondante. Annullare uno di questi vincoli significa traslarlo di una quantità sufficiente da fargli includere tutta la regione ammissibile dell'altro poliedro, come evidenziato in figura 4.

fig. 4: traslazione dei vincoli

Per poter effettuare questa operazione di annullamento di al più un vincolo (o un gruppo di vincoli) tra i due individuati, introduciamo le variabili 0-1 $y_P$ e $y_Q$ che valgono 1 se decidiamo di annullare il vincolo relativo a $P$ o a $Q$, rispettivamente. La formulazione della regione in figura 2 risulta quindi:

$$\begin{eqnarray*} x_2\leq 1\\ x_1 \geq 0\\ x_2 \geq 0\\ x_1 - x_2 \leq 0 + M_... ...2 \leq 1 + M_Qy_Q\\ y_P + y_Q \leq 1\\ y_P, y_Q \in \{0,1\}\\ \end{eqnarray*}$$

Il vincolo $y_P + y_Q \leq 1$ consente di annullare al più uno dei due gruppi di vincoli. La scelta delle due costanti $M_P$ e $M_Q$ deve essere tale da garantire che la regione ammissibile sia completamente contenuta dal vincolo traslato. Nel nostro caso quindi $M_P \geq 1$ e $M_Q \geq 1$.

Un caso particolare di applicazione della tecnica dei vincoli disgiuntivi riguarda i problemi di scheduling di lavori su macchine. Poniamoci il problema di processare $n$ lavori $1,\ldots ,n$ su $m$ macchine denotate da $1,\ldots , m$. Ogni lavoro deve essere eseguito prima sulla macchina 1, poi sulla 2, e così via fino ad essere eseguito al termine sull'ultima macchina $m$. Il tempo di esecuzione del lavoro $j$ sulla macchina $k$ è dato da $s_{jk}, j=1,\ldots ,n$ e $k=1,\ldots ,m$. Le varie macchine possono eseguire un lavoro alla volta e i lavori su ogni macchina devono essere eseguiti fino al termine, cioè non possono essere interrotti e ripresi. Il problema consiste nella determinazione del sequenziamento dei vari lavori sulle diverse macchine con l'obiettivo di minimizzare il tempo di fine dell'ultimo lavoro (in gergo chiamato makespan). Per stabilire il sequenziamento abbiamo bisogno di variabili $t_{jk}$ che fissano il tempo di inizio del lavoro j sulla macchina $k$. Con queste variabili è semplice formulare i vincoli che riguardano la sequenza di lavorazione di ogni singolo lavoro:

$$t_{jk} + s_{jk} \leq t_{jk+1} j=1,\ldots ,n, k=1,\ldots ,m-1$$

il lavoro $j$ non può iniziare ad essere eseguito sulla macchina $k+1$ prima di aver terminato sulla macchina $k$. Per rappresentare correttamente la funzione obiettivo che è di tipo bottleneck (min max) introduciamo una variabile $T$ che sarà maggiore o uguale del tempo di fine dell'ultimo lavoro sull'ultima macchina:

$$t_{jm} + s_{jm} \leq T j=1,\ldots ,n,$$

Ovviamente la funzione obiettivo tenderà a minimizzare $T$, in modo che nella soluzione ottima $T$ assumerà proprio il tempo di fine dell'ultimo lavoro:

$$\min T$$

Non rimane che formulare i vincoli che impediscono la contemporaneità di esecuzione di due lavori sulla stessa macchina. Questa idea di non contemporaneità è resa considerando ogni coppia di lavori $i$ e $j$ e ogni macchina $k$, e imponendo che sulla macchina $k$ o $i$ precede $j$ o $j$ precede $i$, cioè:

$$t_{ik} + s_{ik} \leq t_{jk}$$

oppure

$$t_{jk} + s_{jk} \leq t_{ik}$$

Per esprimere la disgiunzione tra i due vincoli abbiamo bisogno di una variabile 0-1 $y_{ijk}$ che vale 1 se $i$ precede $j$ su $k$ e 0 viceversa. I vincoli (disgiuntivi) sono:

$$t_{ik} + s_{ik} \leq t_{jk} + M(1-y_{ijk}) i, j=1,\ldots ,n, (i­j), k=1,\ldots ,m$$

$$t_{jk} + s_{jk} \leq t_{ik} + My_{ijk} i, j=1,\ldots ,n, (i­j), k=1,\ldots ,m$$

dove $M$ è un valore sufficientemente elevato.

Generalizzando la tecnica dei vincoli disgiuntivi vista per il caso della regione non convessa e per lo scheduling, consideriamo il problema di determinare una soluzione che soddisfi almeno $k$ ( $1\leq k \leq n$) dei vincoli:

$$A_i x \leq b_i, i = 1,\ldots ,n.$$

Sia $M \in \mathbb{R}: A_i x Ðb_i \leq M$, per ogni $x$ ammissibile, $i = 1,\ldots ,n$. Il problema può essere formulato come segue:

$$\begin{eqnarray*} & A_i x \leq b_i + M y_i & i = 1,\ldots ,n,\\ &\sum_{i=1}^n y_i \leq n - k,\\ & y \in \{0,1\}^n.\\ \end{eqnarray*}$$