Esempi di consistenza sui
limiti
X  3Y  5Z
D( X )  [2..7], D(Y )  [0..2], D( Z )  [ 1..2]
Non consistente sui limiti, considera Z=2, poi X-3Y=10
Ma il dominio qui sotto e’ consistente sui limiti:
D( X )  [2..7], D(Y )  [0..2], D( Z )  [0..1]
Confrontare con il dominio consistente sugli iper-archi:
D( X )  {3,5,6}, D(Y )  {0,1,2}, D( Z )  {0,1} 1
Ottenere la consistenza sui
limiti
Dato un dominio D, vogliamo modificare i
limiti dei domini in modod che sia
consistente sui limiti
 Si usano delle regole di propagazione

2
Ottenere la consistenza sui
limiti
Consideriamo il vincolo primitivo X = Y + Z che e’
equivalente alle tre forme:
X YZ Y  X Z
Z  X Y
Ragionando sui valori minimi e massimi:
X  min( D, Y )  min( D, Z )
X  max( D, Y )  max( D, Z )
Y  min( D, X )  max( D, Z )
Z  min( D, X )  max( D, Y )
Y  max( D, X )  min( D, Z )
Z  max( D, X )  min( D, Y )
Regole di propagazione per il vincolo X = Y + Z
3
Ottenere la consistenza sui
limiti
X YZ
D( X )  [4..8], D(Y )  [0..3], D( Z )  [2..2]
Le regole di propagazione determinano che:
( 0  2  ) 2  X  5 (  3  2)
( 4  2  ) 2  Y  6 (  8  2)
(4  3 ) 1  Z  8 (  8  0)
Quindi i domini possono essere ridotti a:
D( X )  [4..5], D(Y )  [2..3], D( Z )  [2..2]
4
Altre regole di propagazione
4W  3 P  2C  9
9 3
2
W   min( D, P)  min( D, C )
4 4
4
9 4
2
P   min( D, W )  min( D, C )
3 3
3
9 4
3
C   min( D, W )  min( D, P)
2 2
2
Dato il dominio iniziale:
D(W )  [0..9], D( P)  [0..9], D(C)  [0..9]
Determiniamo che: W  9 , P  9 , C  9
4
3
2
Nuovo dominio:D(W )  [0..2], D( P)  [0..3], D(C)  [0..4]
5
Disequazioni Y  Z
Le disequazioni generano delle regole di propagazioni
deboli: c’e’ propagazione solo quando una variabile ha
un valore fisso che e’ uguale al minimo o massimo
dell’altra variabile
D(Y )  [2..4], D( Z )  [2..3] no propagation
D(Y )  [2..4], D( Z )  [3..3] no propagation
D(Y )  [2..4], D( Z )  [2..2] prop D(Y )  [ 3..4], D( Z )  [2..2]
6
Moltiplicazione X  Y  Z
Se tutte le variabili sono positive, e’ semplice:
X  min( D, Y )  min( D, Z )
X  max( D, Y )  max( D, Z )
Y  min( D, X ) / max( D, Z )
Z  min( D, X ) / max( D, Y )
Y  max( D, X ) / min( D, Z )
Z  max( D, X ) / min( D, Y )
Esempio: D( X )  [4..8], D(Y )  [1..2], D( Z )  [1..3]
Diventa: D( X )  [4..6], D(Y )  [2..2], D( Z )  [2..3]
Ma se le variabili possono essere 0 o negative?
7
Moltiplicazione X  Y  Z
Calcolare i limiti di X esaminando i valori estremi:
X
 minimum{min( D, Y )  min( D, Z ), min( D, Y )  max( D, Z )
max( D, Y )  min( D, Z ), max( D, Y )  max( D, Z )}
Simile per limite superiore usando il massimo.
Ma questo non funziona per Y e Z? Se min(D,Z) <0
e max(D,Z)>0 non c’e’ nessuna restrizione per Y
X  Y  Z { X  4, Y  d , Z  4 / d }
Stiamo usando numeri reali (es. 4/d)
8
Moltiplicazione X  Y  Z
Possiamo aspettare finche’ il range di Z e’ non
negativo o non positivo e poi usare le regole
Y  minimum{min( D, X ) / min( D, Z ), min( D, X ) / max( D, Z )
max( D, X ) / min( D, Z ), max( D, X ) / max( D, Z )}
Divisione per 0:
 ve
 
0
 ve
 
0
0
 
0
9
Algoritmo per la consistenza
sui limiti
Applica ripetutamente le regole di
propagazione ad ogni vincolo primitivo
finche’ non viene modificato nessun
dominio
 Non dobbiamo ri-esaminare un vincolo
primitivo se i domini delle sue variabili non
sono modificati

10
Esempio di consistenza sui
limiti
Problema dello zaino del ladro (senza whisky)
capacity
profit
4W  3 P  2C  9  15W  10 P  7C  30
1..39],],D
D(W )  [0..0], D( P)  [0
D((C
C)) [[00....49]]
28/ 15
/ 15 PP212
/ 10
CC

0 /760 / 7
WW
 
102
/
10
W 9/4 P9/3 C9/2
Non c’e piu’ nessuna modifica.
Notare che abbiamo dovuto riesaminare il vincolo
di profitto.
11
Risolutore per la consistenza
sui limiti
D := bounds_consistent(C,D)
 if D e’ un dominio falso

 return

if D e’ un dominio valutazione
 return

false
satisfiable(C,D)
return unknown
12
Ricerca con backtracking
combinata con la consistenza
sui limiti

Applicare la consistenza sui limiti prima di
iniziare la ricerca con backtracking e dopo
ogni assegnamento di un valore ad una
variabile
13
Esempio
Problema del ladro
capacity
profit
4W  3 P  2C  9  15W  10 P  7C  30
Dominio corrente:
1
D((W
W))  [[00....9
1..3
00....349]]]
20], D( P)  [0
D((C
C)) [[3
D
9],],D
Consistenza sui limiti iniziale:
W=0
P=1
(0,1,3)
Trovata una soluzione:
return true
14
Esempio
Problema del ladro
capacity
profit
4W  3 P  2C  9  15W  10 P  7C  30
Dominio corrente:
DD
},D
(P
((C
{[00}..4]
D(W
)(W
00],
(P
) )[1{
..33},
D
C
(W)[0)..{

,D
,],DD
(C
) ))
Backtrack
Backtrack
Consistenza sui limiti iniziale:
W=0
P=1
P=2
P=3
(0,1,3)
false
(0,3,0)
W=1
W=2
(1,1,1)
(2,0,0)
15
Non ci sono altre soluzioni
Consistenza generalizzata

Possiamo usare qualunque metodi di consistenza
diversi su vincoli diversi, e comunicheranno
attraverso I dimini delle variabili




node consistency : per vincoli primitivi con 1
arc consistency: per vinoli primitivi con 2 var
bounds consistency: altri vincoli primitivi
A volte possiamo eliminare piu’ valori usando
vincoli ‘’complessi’’ e metodi di consistenza
specializzati
16
Alldifferent

alldifferent({V1,...,Vn}) e’ soddisfatto quando ogni
variabile V1,..,Vn ha un valore diverso

alldifferent({X, Y, Z}) e’ equivalente a
X  Y  X  Z Y  Z

E’ consistente sugli archi con il dominio

D( X )  {1,2}, D(Y )  {1,2}, D( Z )  {1,2}
Ma non c’e’ soluzione!  la consistenza
specializzata per alldifferent puo’ scoprirlo
17
Alldifferent Consistency
Sia c della forma alldifferent(V)
 while esiste v in V dove D(v) = {d}

V
:= V - {v}
 for ogni v’ in V
 D(v’) := D(v’) - {d}
DV := unione di tutti i D(v) per v in V
 if |DV| < |V| then return false domain
 return D

18
Alldifferent Examples
alldifferent ({ X , Y , Z})
D( X )  {1,2}, D(Y )  {1,2}, D( Z )  {1,2}
DV = {1,2}, V={X,Y,Z} quindi scopre la non soddisfacibilita’
alldifferent ({ X , Y , Z , T})
D( X )  {1,2}, D(Y )  {1,2}, D( Z )  {1,2}, D(T )  {2,3,4,5}
DV = {1,2,3,4,5}, V={X,Y,Z,T} non la scopre
Algoritmi basti Xsu matching
massimo
potrebbero
scoprirla:
Y
Z
T
1
2
3
4
5
19
Altri vincoli complessi
cumulative([ S1 ,, Sn ],[ D1 ,, Dn ],[ R1 ,, Rn ], L)

schedulare n lavori con tempi iniziali Si e
durate Di che usano risorse Ri in cui L
risorse sono disponibili in ogni momento
element ( I ,[V1 ,,Vn ], X )

Accesso all’array: se I = i, allora X = Vi e se
X != Vi allora I != i
20
Ottimizzazione per CSPs
Dato che i domini sono finiti, possiamo
usare un risolutore per costruire un
ottimizzatore banale
 retry_int_opt(C, D, f, best)

 D2
:= int_solv(C,D)
 if D2 e’ un dominio falso then return best
 sia sol la soluzione corrispondente a D2
 return retry_int_opt(C /\ f < sol(f), D, f, sol)
21
Esempio
Problema del ladro (ottimizzare il profitto)
minimize
minimize 15
15W
W10
10PP77CCsubject
subjectto
to
capacity
profit
capacity
profit
44W
W33PP22CC99  15
15W
W10
10PP77CC30
30
 15W
D
15
W
10
D(W10
) P[0..715
9C],W
P

[0
9],D
(31
CP) 
 7[0C..9]32
( 31
10)
P
7..C
D
D((W
W))[[00....99],],D
D((PP))[[00....99],],D
D((CC))[[00....99]]
(W) )[0[1....01],],D
D((PP)) [[11....11],],D
D((C
C)) [[31..1
Nessuna
altra soluzione!
3]
Next
First
solution
solution
found:
found: DD(W
sol{W
{W
01
11, C
, C
31}}
, ,PP
Corresponding
Return
la sol. migliore
solution sol
sol ( f )  32
31
22
Backtracking + Ottimizzazione
Dato che il risolutore puo’ usare la ricerca
con backtracking, e’ meglio combinarla con
l’ottimizzazione
 Ad ogni passo della ricerca con
backtracking, se best e’ la soluzione ottima
vista finora, aggiungi il vincolo f < best(f)

23
Esempio
Problema del ladro
capacity
profitavailable)
Smugglers
knapsack problem (whiskey
4W capacity
 3 P  2C  9  15W  10
P  7C  30
profit
W
7C10P
31 7C  30
4W  3 P  2C15
W9  10
 P15
Dominio corrente:
1
D((W
W))  [[00....9
1..3
00....349]]]
20], D( P)  [0
D((C
C)) [[3
D
9],],D
Consistenza sui limiti iniziale:
W=0
P=1
(0,1,3)
Soluzione trovata  aggiungi il
vincolo
24
Esempio
Problema del ladro
capacity
profit
4W  3 P  2C  9  15W  10 P  7C  30
 15W  10 P  7C  32
31
Consistenza sui limiti iniziale:
W=0
P=1
P=2
P=3
(0,1,3)
false
false
W=1
W=2
(1,1,1)
false
Modify
constraint
Return l’ultima
sol (1,1,1)
25
Ottimizzazione con Branch
and Bound


Il metodo precedente, a differenza del simplesso,
non usa la funzione obbiettivo per dirigere la
ricerca
Ottimizzazione branch and bound per (C,f)



Usare il simplesso per trovare una soluzione reale
Se la soluzione e’ intera, stop
Altrimenti scegliere una var x con valore non intero d e
esaminare I problemi
(C  x  d , f ) (C  x  d  , f )

Usare la soluzione ottima corrente per vincolare I
problemi
26
Esempio
Problema del ladro
W
 211 / 4, P  0, CW03}
{W
 10}
{W 
P 20, P  1 / 3, CP
false
{C
W
 6 1/ 4, P W1,
C2 0}
 1 1 / 2{}W W
0 2, P  0C, C
{W 
/ 32, Cfalse
 0}
P 1,1P P5 
{W  2, P
 0, =
C 30
 0}
Soluzione
(2,0,0)
{
 1, C
 1}
W0, C2 Soluzione
{W 
1W
}  1, P
(1,1,1)
= 32
 17 / 4, P 
 3 5false
{W
0, C
/ 2}
C
 21, P  C
Peggio della sol ottima
 10, C  3}
P
W
 03 / 4, W
false {W
27
false
false
Finite Constraint Domains
Summary
CSPs form an important class of problems
 Solving of CSPs is essentially based on
backtracking search
 Reduce the search using consistency
methods



node, arc, bound, generalized
Optimization is based on repeated solving
or using a real optimizer to guide the search
28