Constraint Systems

Modellazione: "La Colazione dei Campioni"

Il cuoco Arturo Pellegnisi della nazionale Italiana di Bocce si trova alle prese con un difficile compito: decidere il menu per il ritiro primaverile dei campioni d'Europa 2009; l'evento, sponsorizzato da “Suprema™ – Campioni in ogni campo”, durerà ben 4 giorni.

Arturo è in special modo preoccupato di cosa servire nei 4 pranzi, ciascuno dei quali consisterà di 3 portate. Come ogni cuoco che si rispetti, egli non servirà mai uno stesso piatto per due giorni di fila; oltre a ciò, la dieta di un campione deve essere equilibrata, così che nel corso del ritiro gli atleti dovranno assumere la medesima quantità di carboidrati, proteine, latticini e fibre.

Modellazione: "La Colazione dei Campioni"

Arturo sceglierà i piatti da servire dalla seguente lista:

Si modelli la scelta del menu come un problema di soddisfacimento di vincoli, e si mostri una possibile soluzione.

Soluzione

• Introduciamo un insieme di variabili per rappresentare la portata $i$-ma del pranzo $j$-mo:

$$P_{i,j} \in \{Ps, Ca, Uo, Fo, Pa, Ve, Fr, In, Yo, Nu\}$$

• I vincoli di non-riproposizione delle portate:

$$\begin{align} & \text{ALLDIFF}([P_{0,0}, P_{1,0}, P_{2,0}, P_{0,1}, P_{1,1}, P_{2,1}])\\ & \text{ALLDIFF}([P_{0,1}, P_{1,1}, P_{2,1}, P_{0,2}, P_{1,2}, P_{2,2}])\\ & \text{ALLDIFF}([P_{0,2}, P_{1,2}, P_{2,2}, P_{0,3}, P_{1,3}, P_{2,3}]) \end{align}$$

• Introduciamo altre variabili per rappresentare il tipo della portata:

$$T_{i,j} \in \{Car, Pro, Lat, Fib\}$$

Soluzione

• Per connettere i due tipi di varibili possiamo usare:

$$\begin{align} & (T_{i,j} = Car) = \max(P_{i,j} = Ps, P_{i,j} = Pa, P_{i,j} = Nu)\\ & (T_{i,j} = Pro) = \max(P_{i,j} = Ca, P_{i,j} = Uo)\\ & (T_{i,j} = Lat) = \max(P_{i,j} = Fo, P_{i,j} = Yo)\\ & (T_{i,j} = Fib) = \max(P_{i,j} = Fr, P_{i,j} = Ve, P_{i,j} = In) \end{align}$$

• L'equilibrio della dieta viene garantito da un GCC:

$$\text{GCC}(T, [Car, Pro, Lat, Fib], [3, 3, 3, 3], [3, 3, 3, 3])$$

Soluzione

Una possibile soluzione:

Esercizio: Propagazione di ${\rm\scriptsize GCC}$

Si consideri questo grafo dei valori per il vincolo ${\rm\scriptsize GCC}$

• Linea continua: flusso > 0
• Linea tratteggiata: flusso = 0

Esercizio: Propagazione di ${\rm\scriptsize GCC}$

Si consideri questo grafo dei valori per il vincolo ${\rm\scriptsize GCC}$

• Etichette sugli archi: flusso [req, cap]
• No etichetta: X [0, 1]

Esercizio: Propagazione di ${\rm\scriptsize GCC}$

Si consideri questo grafo dei valori per il vincolo ${\rm\scriptsize GCC}$

• Si esegua il propagatore e si verifichi se il vincolo è ammissibile
• Si indviduino i comp. fortemente connessi e si effettui il filtering

Soluzione

Innanzitutto occorre ottenere il grafo residuale:

• Se c'è un arco $(i,j)$ del grafo originale
  • Il grafo residuale contiene $(i,j)$ sse $f(i,j) < cap(i,j)$
    • Nel grafo residuale, $(i,j)$ ha capacità $cap(i,j) - f(i,j)$
  • Il grafo residuale contiene $(j,i)$ sse $f(i,j) > req(i,j)$
    • Nel grafo residuale, $(j,i)$ ha capacità $f(i,j) - req(i,j)$

Alcune conseguenze:

• Gli archi tra valori e variabili hanno capacità 1 e richiesta 0
  • Tra di essi vi sarà o un arco $(i,j)$ o un arco $(j,i)$
  • La capacità sarà sempre 1
• Gli archi tra $s$ e le variabili posso avere requisiti e capacità diverse
  • Possono esserci archi in entrambe le direzioni!

Soluzione

Innanzitutto occorre ottenere il grafo residuale:

• Le capacità degli archi del grafo residuale non sono riportate
• Si notino i due archi (arco bidirezionale) tra $s$ e $0$

Soluzione

Poi cerchiamo un percorso aumentante:

Se tra due nodi ci sono due archi (e.g. $s$ e $0$), solo uno di essi sarà utilizzato, perché non si può visitare lo stesso nodo più di una volta

Soluzione

Modifichiamo il flusso ed otteniamo un nuovo grafo residuale:

• Il flusso totale è 4 = numero di variabili
• Quindi il vincolo è feasible

Soluzione

Cerchiamo i componenti fortemente connessi:

Regola: nodi che fanno parte di un ciclo compaiono nello stesso componente fortemente connesso

Soluzione

Cerchiamo i componenti fortemente connessi:

• In questo caso, ogni nodo forma un componente a sé!
• Gli archi con flusso 0 tra componenti diversi vanno eliminati

Soluzione

Ecco il risultato finale:

• I domini finali sono: $x_0 \in \{0\}, x_1 \in \{1\}, x_2 \in \{1\}, x_3 \in \{2\}$

Esercizio: Propagazione e Vincoli Reificati

Si consideri il seguente CSP:

$$\begin{align} \fbox{0}\quad & x_0 + x_1 = x_2\\ \fbox{1}\quad & x_1 = (x_0 \leq 2) + (x_2 = 3) \\ \fbox{2}\quad & x_0 + x_2 \leq 4 \end{align}$$

con: $x_0 \in \{0..4\}, x_1 \in \{0,1\}, x_2 \in \{2,3\}$

Ipotesi:

• Nessun propagatore incrementale
• BC per "$+$" e "$\leq$", GAC per "$=$"

Esercizio: Propagazione e Vincoli Reificati

Si consideri il seguente CSP:

$$\begin{align} \fbox{0}\quad & x_0 + x_1 = x_2\\ \fbox{1}\quad & x_1 = (x_0 \leq 2) + (x_2 = 3) \\ \fbox{2}\quad & x_0 + x_2 \leq 4 \end{align}$$

con: $x_0 \in \{0..4\}, x_1 \in \{0,1\}, x_2 \in \{2,3\}$

• Si mostri la sequenza di attivazione dei vincoli con AC1
• Si mostri anche lo stato dei domini dopo ciascuna attivazione
• Si discuta la propagazione effettuata ad ogni passo
• Dal punto di vista di AC1, si trattino i 3 vincoli come indivisibili

Soluzione

Step 1, vincolo $\fbox{0}$

• È utile "riscrivere" il vincolo mettendo in evidenza i domini

$$\{0..4\} + \{0,1\} = \{2,3\}$$

• Da cui si deduce che:

$$x_0 \in \{1..3\}, x_1 \in \{0,1\}, x_2 \in \{2,3\}$$

Soluzione

Step 2, vincolo $\fbox{1}$

• Riscrivendo il vincolo, otteniamo:

$$\{0,1\} = (\{1..3\} \leq 2) + (\{2,3\} = 3)$$

• I vincoli reificati vanno però trattati a come variabili!
• Il loro dominio corrisponde ai possibili stati del vincolo
• Otteniamo una seconda riscrittura:

$$\{0,1\} = \{0,1\} + \{0,1\}$$

• I vincoli reficati propagano solo se sicuramente veri/falsi
• Non si deduce nulla: i domini restano inalterati

Soluzione

Step 3, vincolo $\fbox{2}$

• Riscrittura: $\{1..3\} + \{2,3\} \leq 4$
• Domini: $x_0 \in \{1..2\}, x_1 \in \{0,1\}, x_2 \in \{2,3\}$

Step 4, vincolo $\fbox{0}$

• Riscrittura: $\{1..2\} + \{0,1\} = \{2,3\}$
• Domini: $---$

Soluzione

Step 5, vincolo $\fbox{1}$

• Riscrittura: $\{0,1\} = (\{1,2\} \leq 2) + (\{2,3\} = 3)$
• E quindi: $\{0,1\} = \{1\} + \{0,1\}$
• Da cui si deduce: $\{1\} = \{1\} + \{0\}$
• I vincoli reificati ora sono sicuramente veri/falsi
• Solo in queste condizioni essi propagano!
  • $(\{2,3\} = 3)$ è falso, quindi $3$ viene eliminato
• Otteniamo i domini: $x_0 \in \{1,2\}, x_1 \in \{1\}, x_2 \in \{2\}$

Soluzione

Step 6, vincolo $\fbox{2}$

• Riscrittura: $\{1,2\} + \{2\} \leq 4$
• Domini: $---$

Step 7, vincolo $\fbox{0}$

• Riscrittura: $\{1,2\} + \{1\} = \{2\}$
• Domini: $x_0 \in \{1\}, x_1 \in \{1\}, x_2 \in \{2\}$

A questo punto tutti i vincoli sono soddisfatti

• Non è più possibie effettuare propagazione
• Descriviamo brevemente il resto dell'esecuzione di AC1

Soluzione

Passi rimanenti di AC1

• Step 8, vincolo $\fbox{1}$, domini: $---$
• Step 9, vincolo $\fbox{2}$, domini: $---$
• Step 10, vincolo $\fbox{0}$, domini: $---$
• Step 11, vincolo $\fbox{1}$, domini: $---$
• Step 12, vincolo $\fbox{2}$, domini: $---$

Esercizio: Progettazione

Sia dato il seguente CSP (un caso particole di Graph coloring):

$$\begin{align} \min z = & \max(x)\\ \text{s.t.: } & {\rm\scriptsize ALLDIFF}([x_0, x_1, x_2, x_3])\\ & {\rm\scriptsize ALLDIFF}([x_2, x_3, x_4, x_5])\\ & x_2 = 1\\ & x_i \in \{0..5\} & \forall i = 0..5 \end{align}$$

Si discutano alcune modalità per rompere eventuali simmetrie

• Sì, la soluzione ottima è ovvia, lo so :-)
• Focalizzatevi lo stesso sul rompere le simmetrie

Soluzione

Il problema presenta diverse simmetrie. In particolare:

• Le variabili all'interno di ciascun ${\rm\scriptsize ALLDIFF}$ sono indistinguibili
• Con la sola eccezione di $x_2$, che è soggetta ad un altro vincolo

È possibile eliminare molte delle le simmetrie usando il metodo lex-leader, nel caso speciale di variabili soggette ad ${\rm\scriptsize ALLDIFF}$

• Basta quindi forzare un ordine sui valori delle varibili in ogni ${\rm\scriptsize ALLDIFF}$
• Una accortezza importante: l'ordine non va imposto su $x_2$!

E.g.:

$$\begin{align} & x_0 < x_1 < x_3\\ & x_3 < x_4 < x_5 \end{align}$$