Domande in preparazione all'esame di Business intelligence e big data m

Programmazione a vincoli – modellazione e strategie di ricerca

La programmazione a vincoli, constraint programming (CP), è un approccio dichiarativo che permette di

risolvere

- I CSP, problemi di soddisfacimento vincoli (constraint satisfaction problem), ovvero variabili da

soddisfare affinché tutti i vincoli siano soddisfatti

- I COP, problemi di ottimizzazione vincolata (constraint optimization problem), dove non abbiamo

solo variabili da soddisfare ma anche funzioni obiettivo, ovvero scopi da massimizzare,

l’assegnamento migliore.

Il CP si contraddistingue per ricco linguaggio di modellazione, prototipazione veloce (4-5h), facile

manutenzione, estendibilità con nuovi vincoli (personalizzazione strategie di ricerca ecc), ottimo framework

per approcci ibridi. È ottimo specialmente per problemi disordinati.

L’approccio schematico alla CP si basa su due fasi, in primo luogo il ragionamento sui vincoli per restringere

le possibilità di scelta (es.sudoku), in secondo luogo la comprensione ed eventuale annullamento di alcune

scelte, ricercando la combinazione che soddisfa il vincolo.

La CP però non è data solo dal ragionamento sui vincoli e dalla ricerca ma anche dalla modellazione:

CP=Modello+Ragionamento sui vincoli+Ricerca

Definiamo il problema a cui siamo interessati: CSP=<X,D,C> dove abbiamo rispettivamente variabili (X),

domini (D), vincoli (C). Un vincolo c(j) è definito sopra un sottoinsieme X(c(j)) delle variabili. L’ambito

(scope) di un vincolo è il sottoinsieme di variabili su cui questo vincolo va a lavorare.

La soluzione di un CSP è un assegnamento di tutte le variabili che sia compatibile con tutti i vincoli. Un CSP

senza soluzione è detto infeasible. Ricordiamo che ogni vincolo è ammissibile se e solo se con domini finiti.

Si usa una rappresentazione intensionale (simbolica), molto più compatta, chiara, meno generale.

Le forme intensionali sono rese possibili dalle librerie di vincoli, una raccolta di tipi di vincoli (ad esempio,

Uguaglianza: notazione x=y, semantica “vincolo soddisfatto se x è uguale a y”).

Il ragionamento sui vincoli parte dal filtering, filtraggio, ovvero la rimozione dal dominio delle variabili

coinvolte i valori che si possono dimostrare incompatibili, infeasible (ad esempio, per il vincolo di

∈ ∈ ∈ ∈

Uguaglianza: prima del filtraggio x {0,1}, y {1,2}, dopo il filtraggio x {1}, y {1}).

La propagazione è il meccanismo con cui il filtraggio applicato su un particolare vincolo riduce il dominio

considerato e può attivare il filtraggio su un altro vincolo. Avviene appunto perché i domini delle variabili

sono stati modificati dal filtraggio del primo vincolo. La propagazione è controllata da un algoritmo di

propagazione, ad esempio l’AC1.

In generale, tuttavia, il filtraggio e la propagazione non sono sufficienti per risolvere un CSP. Dobbiamo

ancora cercare una soluzione. La tipologia di ricerca più semplice è la Depth-First Search (DFS), o “ricerca di

profondità”, anche chiamata ricerca ad albero.

function DFS(CSP):

if una soluzione è stata trovata: return true

if il CSP non è risolvibile: return false

for d in decisions(CSP) //decisioni in fase di ricerca

if DFS(apply(d, CSP)): return true

return false

Costruisce una serie di decisioni, prova ad applicarle, se successo, true, altrimenti backtrack, annullando

l’ultima decisione e provando con la prossima. Se nessuna decisione ha successo, restituisce false e il

problema è insolubile. Un problema è invece irrealizzabile se abbiamo una completa rimozione di valori dal

dominio, condizione sufficiente ma non necessaria in quanto il problema può essere insolubile anche senza

rimozione completa del dominio.

Le decisioni restituite da decisions(CSP) sono vincoli. Applicare una decisione significa applicare il vincolo al

problema. Durante il backtrack il vincolo deve essere rimosso.

È possibile cambiare il criterio per scegliere la variabile su cui fare branching (selezione della variabile) -ad

esempio l’uso di euristiche per la selezione della variabile tramite valore minimo del dominio più piccolo- o

il valore per il branching (selezione del valore) -ad esempio il valore massimo-.

Come scegliere le euristiche? Pensiamo a euristiche specifiche per ogni tipo di problema, o serie di

problemi, che massimizzino la probabilità di soddisfacibilità del problema.

Per velocizzare l’esplorazione dei sotto alberi seguiamo uno schema chiamato principio First-Fail. Facciamo

branching prima sulle variabili che hanno il dominio più piccolo, siccome sono quelle più significative (pochi

valori significa maggiore difficoltà nell’assegnargliene). Se vi si trovano, la propagazione è più forte ed è più

probabile che avvenga. Si cercano dunque prima le variabili che hanno maggiore probabilità di fallimento.

Possibili schemi di branching sono i seguenti:

Strategia di ricerca aggiuntiva per lo scheduling è la seguente (ripresa dalla domanda (3). Per capirla a

fondo prima studiare la domanda (2)):

Selezioniamo i valori per le variabili s(i) in modo da ridurre al minimo il makespan. Aumentare un s(i) non

può migliorare il makespan, perché stiamo cercando di essere il più rapidi possibile. Selezioniamo dunque il

E E

S (i), earliest start time. Selezioniamo la variabile su cui fare branching, di solito quella con S (i) minore. In

caso di pareggi si può ad esempio preferire il minimo LET(i), ovvero minimizzare la deadline. Una volta che

tutte le variabili sono assegnate abbiamo uno scheduling. Questo processo per trovare la soluzione di un

RCPSP è chiamata PRB scheduling, pianificazione basata su regole di priorità. Ottengo così soluzioni sub-

ottime. Per raggiungerne di ottime è necessario fare ricerca e backtracking.

Una strategia di ricerca è il SetTimes, le cui idee principali sono mettere in esecuzione o posticipare

E

l’attività, scegliere sempre un’attività con il minimo S (i), far iniziare le attività in corrispondenza del loro

E

S (i).

SetTimes è molto efficiente in quanto unisce la velocità di PRB di raggiungere una buona soluzione alla

possibilità di esplorare in maniera efficace l’albero di ricerca. È tuttavia una strategia di ricerca incompleta

in quanto non partizioniamo lo spazio di ricerca. Funziona però in quanto si basa su una regola di

dominanza imponendo precedenze implicitamente (dunque non ha senso non far iniziare le attività in

E

corrispondenza del loro S (i), a meno che non siano ritardate da attività precedenti).

Non funziona con funzioni di costo non regolari o vincoli collaterali che alterano la struttura del problema.

Programmazione a vincoli – tipologie di vincoli e algoritmi di filtraggio (è possibile sia discutere di multipli

algoritmi sia andare a fondo nel dettaglio di un particolare algoritmo, a discrezione del candidato)

Esistono vincoli locali, globali, reificati. Locali sono quelli visti nella domanda prima, possono essere ≠, ≤ , ≥ ,

ecc.. (Per i vincoli reificati vedi domanda dopo). Ragionando a livello globale possiamo introdurre un nuovo

vincolo, chiamato AllDifferent(x) dove x è un vettore di

variabili. Siamo di fronte a un diverso tipo di propagazione,

basato sui flussi di rete, migliore e più potente. Quello in figura

è un grafico bipartito, un grafo tale che l’insieme dei suoi

vertici si può partizionare in due sottoinsiemi tali che ogni

vertice di una di queste due parti sia collegato solo a vertici

dell’altra. S viene chiamato nodo source, connesso a tutti i

valori, t nodo sink, connesso a tutte le variabili. Ogni arco ha

capacità pari a 1 e il flusso parte da s e si sposta verso t. Esiste una soluzione se e solo se tutte le variabili

sono assegnate, cioè se esiste un flusso con valore totale pari a X. Se il valore della portata è =X, si ha un

vincolo soddisfacibile.

L’AllDifferent è usato in diverse applicazioni quale ad esempio il partial latin square: vi è la necessità di

colorare ogni riga e colonna di un quadrato in modo che, con 10 colori, su ciascuna riga e colonna ci siano

tutti colori diversi.

Un altro tipo di vincolo globale è il GCC, Global Cardinality Costraint, che permette più assegnazioni rispetto

al precedente AllDifferent. Un esempio di utilizzo è quello per la programmazione di tornei, dove una

squadra deve essere affrontata x volte in gironi e campi diversi. Gli archi in GCC non hanno capacità solo

pari a 1, ma possono essere usati almeno L(i) volte, al massimo U(i) volte. Definiamo l’etichetta [Li,Ui] per

mostrare la domanda e la capacità.

Se abbiamo solo bisogno di contare le occorrenze di un valore, sfruttiamo un altro tipo di vincolo, il

COUNT(X, v, c) dove X è il vettore di variabili intere, v il valore intero e c il numero intero o variabile. Il

vincolo è soddisfatto se il valore v è assunto al massimo c volte in X. (i vettori vengono indicati con lettera

maiuscola).

Se dobbiamo limitare le occorrenze di un singolo valore, abbiamo ATMOST(X, v, c) dove X è il vettore di

variabili intere, v il valore intero e c il numero intero. Il vincolo è soddisfatto se il valore v è assunto meno di

c volte in X.

Altro vincolo ELEMENT(z, V, x) dove z è una variabile di output, V è un vettore di valori (o di variabili) e x è

una variabile indice. Può essere usato per assegnare a degli oggetti le loro proprietà.

Altro è TABLE(X,T) dove X è un vettore di variabili e T un vettore di tuple, corrispondenti agli assegnamenti

validi. Ogni vincolo che agisce su variabili discrete può essere modellato con TABLE. È spesso molto ben

ottimizzato (fino a 1M di righe).

Infine possiamo usare un vincolo globale per ogni risorsa: CUMULATIVE(s, d, r, c) dove s è un vettore di

variabili di inizio attività, d un vettore di durate, r un vettore di requisiti, c la capacità. Le durate e i requisiti

possono essere sia scalari che variabili. La capacità delle risorse non viene mai superata. Il controllo di

fattibilità è facile quando tutte le s(i) sono fisse. Sfortunatamente, il filtraggio è NP-hard.

Filtering, filtraggio, ovvero la rimozione dal dominio delle variabili coinvolte i valori che si possono ∈

dimostrare incompatibili, infeasible (ad esempio, per il vincolo di Uguaglianza: prima del filtraggio x {0,1},

∈ ∈ ∈

y {1,2}, dopo il filtraggio x {1}, y {1}).

Pruning (“potatura”): più precisamente indica l'atto di eliminare un singolo valore, mentre il filtraggio

(filtering) è il processo che guida il pruning.

La propagazione è il meccanismo con cui il filtraggio applicato su un particolare vincolo riduce il dominio

considerato e può attivare il filtraggio su un altro vincolo. Avviene appunto perché i domini delle variabili

sono stati modificati dal filtraggio del primo vincolo. La propagazione è controllata da un algoritmo di

propagazione, ad esempio l’AC1.

Il filtraggio timetable è uno degli algoritmi di filtraggio per il vincolo cumulative, uno dei più veloci. L’idea è

quella di fare affidamento su un profilo di utilizzo minimo, ovvero un consumo di risorsa minimo garantito

per ogni istante temporale. Il profilo viene usato per determinare i limiti delle variabili s(i). Iniziamo

introducendo un po' di notazione considerando alcuni punti temporali notevoli per ogni attività:

- E

Earliest Start Time EST(i) = S (i)

- E

Earliest End Time EET(i) = S (i) + d(i) //d(i) è la durata dell’attività

- L

Latest Start Time LST(i) = S (i)

- L

Latest End Time LET(i) = S (i) + d(i) //d(i) è la durata dell’attività

Se LST(i)<EET(i), allora nell’intervallo LST(i), EET(i) l’attività i sarà sicuramente eseguita, quindi r(i) unità di

risorsa saranno bloccate. Si dice che l’attività ha delle parti obbligatorie. La somma di queste genera il

profilo di utilizzo.

Altra idea possibile è quella di perlustrare, per ogni attività i, la linea temporale e cercare un orario di inizio

adatto, aggiornando di conseguenza il dominio s(i).

Altri propagatori per CUMULATIVE meritano una menzione:

- Edge Finder, che considera le coppie (Ω, i) dove Ω = un insieme di attività e i = le attività da filtrare.

Molto efficace in finestre temporali ristrette;

- Ragionamento energetico dove energia = risorsa richiesta con x durata ragionando sull'energia

richiesta in determinati intervalli di tempo. Se un uso eccessivo viene rilevato → fallimento, se

viene rilevato un potenziale uso eccessivo → potatura del dominio. Approccio interessante ma

raramente utile per alta complessità;

- Timetable Edge Finding, un approccio più moderno che mescola idee da timetable ed edge finder.

Programmazione a vincoli – strategie di ricerca e consistenza

Aggiunta Depth First Search vedi prima. Altra strategia di ricerca poi è la prossima.

Selezioniamo i valori per le variabili s(i) in modo da ridurre al minimo il makespan (tempo totale per la

completa esecuzione). Aumentare un s(i) non può migliorare il makespan, perché stiamo cercando di essere

E

il più rapidi possibile. Selezioniamo dunque il S (i), earliest start time. Selezioniamo la variabile su cui fare

E

branching, di solito quella con S (i) minore. In caso di pareggi si può ad esempio preferire il minimo LET(i),

ovvero minimizzare la deadline. Una volta che tutte le variabili sono assegnate abbiamo uno scheduling.

Questo processo per trovare la soluzione di un RCPSP è chiamata PRB scheduling, pianificazione basata su

regole di priorità. Ottengo così soluzioni sub-ottime. Per raggiungerne di ottime è necessario fare ricerca e

backtracking.

Una strategia di ricerca è il SetTimes, le cui idee principali sono mettere in esecuzione o posticipare

E

l’attività, scegliere sempre un’attività con il minimo S (i), far iniziare le attività in corrispondenza del loro

E

S (i).

SetTimes è molto efficiente in quanto unisce la velocità di PRB di raggiungere una buona soluzione alla

possibilità di esplorare in maniera efficace l’albero di ricerca. È tuttavia una strategia di ricerca incompleta

in quanto non partizioniamo lo spazio di ricerca. Funziona però in quanto si basa su una regola di

dominanza imponendo precedenze implicitamente (dunque non ha senso non far iniziare le attività in

E

corrispondenza del loro S (i), a meno che non siano ritardate da attività precedenti).

Non funziona con funzioni di costo non regolari o vincoli collaterali che alterano la struttura del problema.

Consistenza: possiamo rimuovere tutti e solamente i valori sprovvisti di supporto. Quando abbiamo

terminato, possiamo dire che la consistenza ad arco vale per il vincolo c (vincolo c AC (arcoconsistente)). Il

nostro CSP è consistente se e solo se tutti i vincoli sono AC. La condizione è necessaria ma non sufficiente in

quanto si possono avere dei vincoli che mettono in connessione più variabili al tempo stesso. L’Arc

Consistency ragiona solo a coppie e fornisce garanzie solo per un unico vincolo. Per questo motivo diciamo

che l’AC è una forma di consistenza locale. Esiste un modo per imporre una consistenza globale? Sì, ma è

complesso quanto risolvere il problema. La complessità di un algoritmo di filtraggio è molto importante.

Vengono infatti eseguite molte operazioni per ogni nodo di ricerca e la strategia di ricerca esplora un

numero esponenziale di nodi. Come conseguenza si ha un forte impatto sulla performance.

Articolando il procedimento per punti,

1. Per ogni variabile (e.g. x) salviamo il valore massimo e minimo del dominio xMAX <-> max(D(x))

xMIN <-> min(D(x))

2. Sulla base di xMAX e xMIN calcoliamo il massimo e minimo per y. Lby = lower bound (limite

inferiore) e Uby = upper bound (limite superiore)

3. Rimuoviamo valori imponendo yMIN = lby e yMAX = uby

Procedendo in questo modo stiamo imponendo la “consistenza di limite” meglio nota come

boundconsistency (BC). Un vincolo c su x e y è bound-consistent se e solo se xMIN e xMAX hanno supporto

in (yMIN, yMAX) e viceversa.

Quindi nel complesso possiamo dire che AC è il meglio che possiamo fare, ma potrebbe essere inefficiente.

BC è molto più efficiente ma può rimuovere meno valori. Sia AC che BC sono incomplete, occorre quindi

effettuare un’ulteriore ricerca. Con AC dedichiamo più tempo alla propagazione ma meno alla ricerca. Con

BC viceversa. È un trade-off. In alcuni casi un approccio è migliore dell’altro ma non sempre la risposta è

banale. AC e BC non sono mutuamente esclusive, anzi solitamente si applicano insieme. Entrambe non

garantiscono di arrivare ad una soluzione.

Programmazione a vincoli – consistenza e vincoli globali

Consistenza: possiamo rimuovere tutti e solamente i valori sprovvisti di supporto. Quando abbiamo

terminato, possiamo dire che la consistenza ad arco vale per il vincolo c (vincolo c AC (arcoconsistente)). Il

nostro CSP è consistente se e solo se tutti i vincoli sono AC. La condizione è necessaria ma non sufficiente in

quanto si possono avere dei vincoli che mettono in connessione più variabili al tempo stesso. L’Arc

Consistency ragiona solo a coppie e fornisce garanzie solo per un unico vincolo. Per questo motivo diciamo

che l’AC è una forma di consistenza locale. Esiste un modo per imporre una consistenza globale? Sì, ma è

complesso quanto risolvere il problema. La complessità di un algoritmo di filtraggio è molto importante.

Vengono infatti eseguite molte operazioni per ogni nodo di ricerca e la strategia di ricerca esplora un

numero esponenziale di nodi. Come conseguenza si ha un forte impatto sulla performance.

Articolando il procedimento per punti,

1. Per ogni variabile (e.g. x) salviamo il valore massimo e minimo del dominio xMAX <-> max(D(x))

xMIN <-> min(D(x))

2. Sulla base di xMAX e xMIN calcoliamo il massimo e minimo per y. Lby = lower bound (limite

inferiore) e Uby = upper bound (limite superiore)

3. Rimuoviamo valori imponendo yMIN = lby e yMAX = uby

Procedendo in questo modo stiamo imponendo la “consistenza di limite” meglio nota come

boundconsistency (BC). Un vincolo c su x e y è bound-consistent se e solo se xMIN e xMAX hanno supporto

in (yMIN, yMAX) e viceversa.

Quindi nel complesso possiamo dire che AC è il meglio che possiamo fare, ma potrebbe essere inefficiente.

BC è molto più efficiente ma può rimuovere meno valori. Sia AC che BC sono incomplete, occorre quindi

effettuare un’ulteriore ricerca. Con AC dedichiamo più tempo alla propagazione ma meno alla ricerca. Con

BC viceversa. È un trade-off. In alcuni casi un approccio è migliore dell’altro ma non sempre la risposta è

banale. AC e BC non sono mutuamente esclusive, anzi solitamente si applicano insieme. Entrambe non

garantiscono di arrivare ad una soluzione.

Vincoli globali: ragionando a livello globale possiamo introdurre un nuovo vincolo, chiamato AllDifferent(x)

dove x è un vettore di variabili. Siamo di fronte a un diverso tipo di propagazione, basato sui flussi di rete,

migliore e più potente. Quello in figura è un grafico bipartito,

un grafo tale che l’insieme dei suoi vertici si può partizionare in

due sottoinsiemi tali che ogni vertice di una di queste due parti