Constraint Systems

Modellazione: "L'impresa di Famiglia"

C'era una volta in un paese lontano lontano la “Mastro Geppetto” Srl, una piccola impresa familiare condotta dall'esperto carpentiere Geppetto e dal suo figlio Pinocchio. Dopo un avvio piuttosto turbolento gli affari della società andavano a gonfie vele, anche perché il piccolo Pinocchio, essendo un burattino, non solo era instancabile, ma poteva industriarsi in barba alla legislazione sul lavoro minorile.

Un giorno Pinocchio comunica al papà di avere ricevuto un’ottima proposta per diventare un bambino vero: il buon Geppetto, lieto per la notizia, decide di cogliere l'occasione per andare in pensione, logicamente dopo aver messo da parte un gruzzoletto per potersi mantenere. Al momento della comunicazione della novità da parte di Pinocchio, i due hanno in magazzino 40 quintali di legna.

Modellazione: "L'impresa di Famiglia"

Pinocchio diventerà un bambino in carne ed ossa di lì a 60 giorni: per quella data Geppetto dovrà aver guadagnato almeno 20 zecchini. La lista delle commesse in sospeso della società conta le seguenti voci:

Modellazione: "L'impresa di Famiglia"

Occorre decidere quali commesse accettare ed indicare in che giorni iniziare a lavorarvi. Si noti che la “Mastro Geppetto” riesce a portare avanti al massimo due commesse contemporaneamente. Si modelli il problema come un CSP e si mostri una possibile soluzione. Si ricordi la possibilità di utilizzare meta-vincoli.

Soluzione

Una variabile binaria $A_i$ per ogni commessa, con $A_i = 1$ se la commessa è accettata, $0$ altrimenti. Una variabile di start $S_i$ per ogni commessa, con dominio:

$$\begin{align} & S_1 \in \{0..40\}, S_2 \in \{0..35\}, S_3 \in \{0..50\}, S_4 \in \{0..30\},\\ & S_5 \in \{0..30\}, S_6 \in \{0..20\}, S_7 \in \{0..35\} \end{align}$$

Vincolo sulla legna disponibile:

$$30\,A_1 + 7\,A_2 + 1\,A_3 + 20\,A_4 + 10\,A_5 + 20\,A_6 + 12\,A_7 \leq 40$$

Vincolo sul profitto da realizzare:

$$10\,A_1 + 4\,A_2 + 5\,A_3 + 8\,A_4 + 6\,A_5 + 2\,A_6 + 5\,A_7 \geq 20$$

Soluzione

Vincolo sulla capacità produttiva dell'azienda

$${\rm\scriptsize CUMULATIVE}([S_1..S_7], [20, 25, 10, 30, 30, 40, 25], [A_1..A_7], 2)$$

• Si ricordi che durate e requisiti nel vincolo ${\rm\scriptsize CUMULATIVE}$ possono essere delle variabili decisionali.

Una possibile soluzione (commesse 2, 3, 4, 5):

$$\begin{align} & A = [0, 1, 1, 1, 1, 0, 0]\\ & S = [0, 0, 0, 10, 25, 0, 0] \end{align}$$

Si noti che il giorno di inizio lavori per le commesse non selezionate non ha significato.

Esercizio: Filtering per ${\rm\scriptsize CUMULATIVE}$

Dato un vincolo ${\rm\scriptsize CUMULATIVE}$ con capacità 3 e le seguenti attività:

Si mostri l'esecuzione del propagatore "timetable" per l'attività 5.

Esercizio: Filtering per ${\rm\scriptsize CUMULATIVE}$

In particolare, sulla griglia seguente:

• Si mostri il profilo di utilizzo minimo della risorsa
• Si individuino le posizione del cursore ed il suo stato
• Si specifichi in che modo viene tagliato il dominio di $s_5$

Soluzione

È utile iniziare calcolando i valori di $LST_i$ ed $EET_i$:

In modo da determinare le parti obbligatorie

Soluzione

Si può quindi disegnare il profilo:

Soluzione

Quindi si possono evidenziare:

• Il dominio di $s_5$
• La posizione di $s_5 + d_5$

Soluzione

A questo punto si possono determinare le posizioni del cursore:

• C = "checking", S = "seeking"
• C/S -- S/C = passaggio da "checking" a "seeking" e vice-versa

Soluzione

Il dominio finale di $s_5$ è ${7}$

Esercizio: Filtering per ${\rm\scriptsize SUM}$

Si consideri il seguente CSP:

$$\begin{align} & {\rm\scriptsize SUM}(z, x)\\ & x_0 \in \{-1..2\}\\ & x_1 \in \{0..1\}\\ & x_2 \in \{-2..1\}\\ & x_3 \in \{0..1\}\\ & z \in \{-10..10\}\\ \end{align}$$

• Si mostri come la variabile $z$ viene tagliata dall'algoritmo di filtering non-incrementale per ${\rm\scriptsize SUM}$
• Si fornisca la formula utilizzata e la si discuta brevemente

Esercizio: Filtering per ${\rm\scriptsize SUM}$

Si supponga ora che il dominio di $x_2$ venga modificato come segue:

$$\{-2..1\} \longrightarrow \{0..1\}$$

• Come viene aggiornato il dominio di $z$? Si utilizzi questa volta la regola di aggiornamento incrementale.
• Si fornisca la formula utilizzata e la si discuta brevemente.

Esercizio: Progettazione

Sia dato un problema combinatorio definito su un insieme di $n$ attività. Per ogni attività occorre decidere l'istante di esecuzione.

• Tutte le attività hanno durata 1
• L'istante di esecuzione $i$-mo deve essere nell'intervallo $[l_i, u_i]$
• Le attività sono soggette ad un insieme $P$ di relazioni di precedenza, rappresentate come coppie $(i, j)$
• Le relazioni di precedenza formano un grafo aciclico
• Le relazioni di precedenza sono opzionali

L'obiettivo è massimizzare il numero di relazioni di precedenza soddisfatte

Esercizio: Progettazione

Il problema è stato modellato nel modo seguente:

$$\begin{align} \min \ & z = \sum_{(i,j) \in P} x_{ij}\\ & x_{ij} \Leftrightarrow s_i + 1 \leq s_j && \forall (i,j) \in P\\ & s_i \in \{l_i..u_i\} && \forall i = 0..n-1\\ & x_{ij} \in \{0, 1\} && \forall (i,j) \in P \end{align}$$

Dove:

• $s_i$ rappresenta l'istante di esecuzione dell'attività $i$
• $x_{ij}$ vale 1 sse la precedenza $(i,j)$ è soddisfatta

Si progetti una possibile strategia di ricerca e la si discuta.

Soluzione

In questo caso, ogni soluzione è buona. Si tratta solo di fornire argomentazioni valide.

Una strategia di ricerca particolarmente buona per questo problema opera in due fasi:

Fase 1:

Branching di tipo $x_{ij} = 1$ / $x_{ij} \neq 0$ sulle variabili $x_{ij}$

• I vincoli di precedenza sono molto facili da gestire una volta che tutte le variabili $x_{ij}$ sono assegnate
• Inoltre, la funzione obiettivo dipende direttamente dalle variabili $x_{ij}$
• Scegliendo $x_{ij} = 1$ come ramo sinistro ci indirizziamo verso soluzioni di buona qualità

Soluzione

In questo caso, ogni soluzione è buona. Si tratta solo di fornire argomentazioni valide.

Una strategia di ricerca particolarmente buona per questo problema opera in due fasi:

Fase 2:

Branching di tipo $s_i = \underline{s}_i$, senza backtracking

• Poiché le relazioni di precedenza formano un grafo aciclico, la propagazione dei vincoli di precedenza è sufficiente a garantire la soddisfacibilità
• Possiamo sempre assegnare $s_i$ al suo valore minimo ed essere sicuri che troveremo una soluzione ammissibile, se questa esiste