Logické programování s omezujícími podmínkami
Constraint Logic Programming: CLP
CP: elektronické materiály
Dechter, R. Constraint Processing. Morgan Kaufmann Publishers, 2003.
i* http://www.ics.uci.edu/~dechter/books/materials.html prUsvitky ke knize
JS> Barták R. Prednáška Omezující podmínky na MFF UK, Praha.
http://kti.ms.mff.cuni.cz/~bartak/podminky/index.html
M SICStus Prolog User's Manual. Kapitola o CLP(FD).
J* http://www.fi.muni.cz/~hanka/sicstus/doc/html/
-í* Príklady v distribuci SICStus Prologu: cca 60 príkladu, zdrojový kód
v lib/sicstus-*/library/clpfd/examples/
Hana Rudová, Logické programování I, 26. dubna 2011
2
Logické programování s omezujícími podmínkami
Probírané oblasti
M Obsah
úvod: od LP k CLP & základy programování
a základní algoritmy pro rešení problémů s omezujícími podmínkami
Hana Rudová, Logické programování I, 26. dubna 2011
3
Logické programování s omezujícími podmínkami
Probírané oblasti
M Obsah
úvod: od LP k CLP & základy programování
a základní algoritmy pro rešení problémů s omezujícími podmínkami
ii> Príbuzné prednášky na FI
s PA163 Programování s omezujícími podmínkami viz interaktivní osnova IS
*> PA167 Rozvrhování
-v http://www.fi.muni.cz/~hanka/rozvrhovani
zahrnuty CP techniky pro rešení rozvrhovacích problémU
Hana Rudová, Logické programování I, 26. dubna 2011
3
Logické programování s omezujícími podmínkami
Historie a současnost
& 1963 interaktivní grafika (Sutherland: Sketchpad)
M Polovina 80. let: logické programování omezujícími podmínkami
& Od 1990: komerCní využití
JS* Už v roce 1996: výnos rádove stovky milionů dolarU
& Aplikace - príklady
a Lufthansa: krátkodobé personální plánování
reakce na zmeny pri doprave (zpoždení letadla, ...) minimalizace zmeny v rozvrhu, minimalizace ceny
J* Nokia: automatická konfigurace sw pro mobilní telefony
Jt Renault: krátkodobé plánování výroby, funkcní od roku 1995
Hana Rudová, Logické programování I, 26. dubna 2011
4
Logické programování s omezujícími podmínkami
Omezení (constraint)
JS> Dána
a množina (doménových) proměnných Y = {yi,... ,^^1 koneCná množina hodnot (doména) D = {D1,... ,Dk}
Omezení c na Y je podmnožina D1 x ... x Dk
a omezuje hodnoty, kterých mohou proměnné nabývat současně
Hana Rudová, Logické programování I, 26. dubna 2011
5
Logické programování s omezujícími podmínkami
Omezení (constraint)
JS> Dána
a množina (doménových) proměnných Y = {yi,... ,^^1 koneCná množina hodnot (doména) D = {D1,... ,Dk}
Omezení c na Y je podmnožina D1 x ... x Dk
a omezuje hodnoty, kterých mohou proměnné nabývat současně
Příklad:
proměnné:
A,B
-i- domény:
{0,1} pro A
{1,2} pro B
omezení:
nebo
(A,B) g {(0,1),(0,2),(1,2)}
Hana Rudová, Logické programování I, 26. dubna 2011
Logické programování s omezujícími podmínkami
Omezení (constraint)
JS> Dána
a množina (doménových) proměnných Y = {y^... ,^^1 koneCná množina hodnot (doména) D = {D1,... ,Dk}
Omezení c na Y je podmnožina D1 x ... x Dk
a omezuje hodnoty, kterých mohou proměnné nabývat současně
Ji Príklad:
-fc promenné: A,B
-i- domény: {0,1} pro A      {1,2} pro B
omezení: A=B      nebo      (A,B) g {(0,1),(0,2),(1,2)}
& Omezení c definováno na y1, ...yk je splneno, pokud pro d1 g D1, ...dk g Dk platí (d1,... dk) g c
-i* príklad (pokračování): omezení splneno pro (0,1), (0, 2), (1,2), není splneno pro (1,1)
Hana Rudová, Logické programování I, 26. dubna 2011
5
Logické programování s omezujícími podmínkami
Problém splňování podmínek (CSP)
C Dána
a konečná množina proměnných X = {xi,... , xn}
it konečná množina hodnot (doména) D = {D1,... ,Dn} s> konečná množina omezení C = {c1,cm}
omezení je definováno na podmnožině X
Problém splňování podmínek je trojice (X,D,C) (constraint satisfaction problem)
Hana Rudová, Logické programování I, 26. dubna 2011
6
Logické programování s omezujícími podmínkami
Problém splňování podmínek (CSP)
C Dána
a konečná množina proměnných X = {xi,... , xn}
it konečná množina hodnot (doména) D = {D1,... ,Dn} it konečná množina omezení C = {c1,cm} omezení je definováno na podmnožině X
Problém splňování podmínek je trojice (X,D,C) (constraint satisfaction problem)
M Príklad:
it promenne:
A,B,C
Jt domeny:
{0,1} pro A
{1,2} pro B
{0,2} pro C
omezení:
A=B, B=C
Hana Rudová, Logické programování I, 26. dubna 2011
6
Logické programování s omezujícími podmínkami
Řešení CSP
■v
ŘásteCné ohodnocení promenných (d1,dk),k < n
s* nekteré promenné mají přiřazenu hodnotu Úplné ohodnocení promenných (d1,dn) & všechny promenné mají prirazenu hodnotu
Hana Rudová, Logické programování I, 26. dubna 2011
7
Logické programování s omezujícími podmínkami
Řešení CSP
■v
Řástecné ohodnocení proměnných (d1,dk),k < n s* některé proměnné mají přiřazenu hodnotu Úplné ohodnocení proměnných (d1,dn) & všechny proměnné mají přiřazenu hodnotu Řešení CSP
-fc úplné ohodnocení promenných, které spinuje všechna omezení s (didn) g Di x ... x Dn je rešení (X, D, C) pro každé ci g C na xii,...xik platí (dii,...dik) g a
Hana Rudová, Logické programování I, 26. dubna 2011
7
Logické programování s omezujícími podmínkami
Řešení CSP
■v
Řástecné ohodnocení promenných (d1,dk),k < n s* nekteré promenné mají prirazenu hodnotu Úplné ohodnocení promenných (d1,dn) & všechny promenné mají prirazenu hodnotu Řešení CSP
-fc úplné ohodnocení promenných, které splnuje všechna omezení s (d1dn) g D1 x ... x Dn je rešení (X, D, C) pro každé ci g C na xi1,...xik platí (di1,...dik) g a
Hledáme: jedno nebo
všechna rešení nebo
optimální r ešení (vzhledem k objektivní funkci)
Hana Rudová, Logické programování I, 26. dubna 2011
7
Logické programování s omezujícími podmínkami
Příklad: jednoduchý školní rozvrh
proměnné: Jan, Petr, ... domény: (3,4, 5,6}, {3,4},... omezení: a11_distinct([Jan,Petr,...])
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
Hana Rudová, Logické programování I, 26. dubna 2011
8
Logické programování s omezujícími podmínkami
Příklad: jednoduchý školní rozvrh
proměnné: Jan, Petr, ...
domény: (3,4, 5,6}, {3,4},...
omězění: all_distinct([Jan,Petr,...])
částečné ohodnocení: Jan=6, Anna=5, Marie=1
úplné ohodnocení:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Mariě=6
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
Hana Rudová, Logické programování I, 26. dubna 2011
8
Logické programování s omezujícími podmínkami
Příklad: jednoduchý školní rozvrh
proměnné: Jan, Petr, ...
domény: (3,4, 5,6}, (3,4},...
omězění: all_distinct([Jan,Petr,...])
částečné ohodnocení: Jan=6, Anna=5, Marie=1
úplné ohodnocení:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Mariě=6 rěšění CSP:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Marie=1
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
všechna řešení: ještě Jan=6, Petr=4, Anna=5, Ota=2, Eva=3, Marie=1
Hana Rudová, Logické programování I, 26. dubna 2011
8
Logické programování s omezujícími podmínkami
Príklad: jednoduchý školní rozvrh
proměnné: Jan, Petr, ... domény: (3,4, 5,6}, {3,4},... omězění: all_distinct([Jan,Petr,...]) částečné ohodnocení: Jan=6, Anna=5, Marie=1 úplné ohodnocení:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Mariě=6 rěšění CSP:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Marie=1
všechna rěšění: ještě Jan=6, Pětr=4, Anna=5, Ota=2, Eva=3, Marie=1
optimalizace: ženy ucí co nejdříve
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
Hana Rudová, Logické programování I, 26. dubna 2011
8
Logické programování s omezujícími podmínkami
Príklad: jednoduchý školní rozvrh
& promenné: Jan, Petr, ...
-i* domény: {3,4, 5,6}, {3,4},...
M omezení: all_distinct([Jan,Petr,...])
JS> cástecné ohodnocení: Jan=6, Anna=5, Marie=1
JS> úplné ohodnocení:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Marie=6
řešení CSP:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Marie=1
& všechna rešení: ješte Jan=6, Petr=4, Anna=5, Ota=2, Eva=3, Marie=1
& optimalizace: ženy ucí co nejdríve
Anna+Eva+Marie #= Cena minimalizace hodnoty promenné Cena optimální rešení: Jan=6, Petr=4, Anna=5, Ota=2, Eva=3, Marie=1
Hana Rudová, Logické programování I, 26. dubna 2011 8 Logické programování s omezujícími podmínkami
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
CLPCFD) program
& Základní struktura CLP programu
1. definice proměnných a jejich domén
2. definice omezení
3. hledání rešení
Hana Rudová, Logické programování I, 26. dubna 2011 9 Logické programování s omezujícími podmínkami
CLPCFD) program
& Základní struktura CLP programu
1. definice proměnných a jejich domén
2. definice omezení
3. hledání rešení
& (1) a (2) deklarativní cást
modelování problému a vyjádření problému splnování podmínek
Hana Rudová, Logické programování I, 26. dubna 2011 9 Logické programování s omezujícími podmínkami
CLPCFD) program
-i* Základní struktura CLP programu
1. definice proměnných a jejich domén
2. definice omezení
3. hledání r ešení
ü> (1) a (2) deklarativní cást
modelování problému a vyjád rení problému splnování podmínek
(3) r ídící cást
& prohledávání stavového prostoru r ešení
a procedura pro hledání r ešení (enumeraci) se nazývá labeling
a umožní nalézt jedno, všechna nebo optimální řešení
Hana Rudová, Logické programování I, 26. dubna 2011 9 Logické programování s omezujícími podmínkami
Kód CLPCFD) programu
% základní struktura CLP programu solve( Variables ) :-
declare_variables( Variables ), domain([Jan],3,6], ...
Hana Rudová, Logické programování I, 26. dubna 2011
10
Logické programování s omezujícími podmínkami
Kód CLPCFD) programu
% základní struktura CLP programu
solve( Variables )
declare_variables( Variables ), post_constraints( Variables ),
domain([Jan],3,6], ... all_distinct([Jan,Petr,...])
Hana Rudová, Logické programování I, 26. dubna 2011
10
Logické programování s omezujícími podmínkami
Kód CLPCFD) programu
% základní struktura CLP programu solve( Variables )
declare_variables( Variables ), domain([Jan],3,6], ...
post_constraints( Variables ), all_distinct([Jan,Petr,...])
labeling( Variables ).
Hana Rudová, Logické programování I, 2G. dubna 20ll
lO
Logické programování s omezujícími podmínkami
Kód CLP(FD) programu
% základní struktura CLP programu solve( Variables ) :-
dec1are_variab1es( Variables ), domain([Jan],3,6], ...
post_constraints( Variables ), a11_distinct([Jan,Petr,...])
labelingC Variables ).
% triviální labeling labelingC [] )■ labelingC [Var|Rest]   ) :-fd_min(Var,Min),
C Var#=Min, labelingC Rest )
% výber nejmenší hodnoty z domény
Hana Rudová, Logické programování I, 26. dubna 20ll
10
Logické programování s omezujícími podmínkami
Kód CLPCFD) programu
% základní struktura CLP programu so1ve( Variables ) :-
dec1are_variab1es( Variables ), domain([Jan],3,6], ...
post_constraints( Variables ), a11_distinct([Jan,Petr,...])
1abe1ing( Variables ).
% triviální labeling 1abe1ing( [] ). 1abe1ing( [Var|Rest]   ) :-
fd_min(Var,Min), % výber nejmenší hodnoty z domény
( Var#=Min, 1abe1ing( Rest )
■
Var#>Min , 1abe1ing( [Var|Rest] )
Hana Rudová, Logické programování I, 26. dubna 2011 10 Logické programování s omezujícími podmínkami
Príklad: algebrogram
Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
SEND + MORE = MONEY rUzná písmena mají prirazena různé cifry s S a M nejsou 0
Hana Rudová, Logické programování I, 26. dubna 2011
Logické programování s omezujícími podmínkami
Příklad: algebrogram
Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
SEND + MORE = MONEY různá písmena mají přiřazena různé cifry s S a M nejsoů 0
domain([E,N,D,O,R,Y], 0, 9), domain([S,M],1,9)
Hana Růdová, Logické programování I, 26. důbna 2011
11
Logické programování s omezujícími podmínkami
Příklad: algebrogram
Prirad'te cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
SEND + MORE = MONEY ruzná písmena mají přiřazena různé cifry s S a M nejsou 0
domain([E,N,D,O,R,Y], 0, 9), domain([S,M],1,9)
1000*S + 100*E + 10*N + D + 1000*M + 100*0 + 10*R + E
#=   10000*M + 1000*0 + 100*N + 10*E + Y
Hana Rudová, Logické programování I, 26. dubna 2011
11
Logické programování s omezujícími podmínkami
Príklad: algebrogram
Prirad'te cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
SEND + MORE = MONEY mzná písmena mají prirazena různé cifry s S a M nejsou 0
domain([E,N,D,O,R,Y], 0, 9), domain([S,M],1,9)
1000*S + 100*E + 10*N + D + 1000*M + 100*0 + 10*R + E
#=   10000*M + 1000*0 + 100*N + 10*E + Y
all_distinct( [S,E,N,D,M,0,R,Y] )
Hana Rudová, Logické programování I, 26. dubna 2011
11
Logické programování s omezujícími podmínkami
Príklad: algebrogram
Prirad'te cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
SEND + MORE = MONEY mzná písmena mají prirazena různé cifry s S a M nejsou 0
domainC[E,N,D,O,R,Y], G, 9), domainC[S,M],l,9)
lGGG*S + lGG*E + lG*N + D + lGGG*M + lGG*O + lG*R + E
#=   lGGGG*M + lGGG*O + lGG*N + lG*E + Y
a11_distinctC [S,E,N,D,M,O,R,Y] ) 1abe1ingC [S,E,N,D,M,O,R,Y] )
Hana Rudová, Logické programování I, 26. dubna 20ll
Logické programování s omezujícími podmínkami
Od LP k CLP I.
-í* CLP: rozšírení logického programování o omezující podmínky -í* CLP systémy se liší podle typu domény -i- CLP(a)   generický jazyk
-fc CLP(FD)   domény promenných jsou konecné (Finite Domains) 3» CLP(R)   doménou promenných je množina reálných císel
Hana Rudová, Logické programování I, 26. dubna 2011
12
Logické programování s omezujícími podmínkami
Od LP k CLP I.
-í* CLP: rozšír ení logického programování o omezující podmínky -í* CLP systémy se liší podle typu domény -i- CLP(a)   generický jazyk
-fc CLP(FD)   domény promenných jsou koneCné (Finite Domains) 3» CLP(R)   doménou promenných je množina reálných císel
C Cíl
± využít syntaktické a výrazové p rednosti LP dosáhnout vetší efektivity
Hana Rudová, Logické programování I, 26. dubna 2011
12
Logické programování s omezujícími podmínkami
Od LP k CLP I.
-í* CLP: rozšírení logického programování o omezující podmínky -í* CLP systémy se liší podle typu domény -i- CLP(a)   generický jazyk
-fc CLP(FD)   domény promenných jsou konecné (Finite Domains) 3» CLP(R)   doménou promenných je množina reálných císel
C Cíl
± využít syntaktické a výrazové prednosti LP
dosáhnout vetší efektivity
Unifikace v LP je nahrazena splňováním podmínek
J* unifikace se chápe jako jedna z podmínek A = B
M A #< B,   A in 0..9,   domain([A,B],0,9), all_distinct([A,B,C])
Hana Rudová, Logické programování I, 26. dubna 2011 12 Logické programování s omezujícími podmínkami
Od LP k CLP II.
Pro řešení podmínek se používají konzistenCní techniky
it consistency techniques, propagace omezení (constraint propagation)
Jt omezení: A in 0..2, B in 0..2, B #< A
Hana Rudová, Logické programování I, 26. dubna 2011
13
Logické programování s omezujícími podmínkami
Od LP k CLP II.
Pro řešení podmínek se používají konzistenCní techniky
it consistency techniques, propagace omezení (constraint propagation)
Jt omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
Hana Rudová, Logické programování I, 26. dubna 2011
13
Logické programování s omezujícími podmínkami
Od LP k CLP II.
Pro řešení podmínek se používají konzistenCní techniky
it consistency techniques, propagace omezení (constraint propagation)
Jt omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky
Hana Rudová, Logické programování I, 26. dubna 2011
13
Logické programování s omezujícími podmínkami
Od LP k CLP II.
& Pro řešení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
Á> omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
ii> Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky JS> Prohledávání doplneno konzistenCními technikami
A in 1..2, B in 0..1, B #< A
Hana Rudová, Logické programování I, 26. dubna 2011 13 Logické programování s omezujícími podmínkami
Od LP k CLP II.
JS> Pro řešení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
£> omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
iS> Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky JS> Prohledávání doplneno konzistenCními technikami
A in 1..2, B in 0..1, B #< A -fc po provedení A #=1      se z B #< A se odvodí:      B #= 0
Hana Rudová, Logické programování I, 26. dubna 2011
13
Logické programování s omezujícími podmínkami
Od LP k CLP II.
& Pro rešení podmínek se používají konzistenCní techniky
it consistency techniques, propagace omezení (constraint propagation)
Jt omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
ii> Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky JS> Prohledávání doplneno konzistenCními technikami
A in 1..2, B in 0..1, B #< A it po provedení A #=1      se z B #< A se odvodí:      B #= 0
& Podmínky jako výstup
it kompaktní reprezentace nekonecného poctu r ešení, výstup lze použít jako vstup
Hana Rudová, Logické programování I, 26. dubna 2011
13
Logické programování s omezujícími podmínkami
Od LP k CLP II.
& Pro r ešení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
it omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
ii> Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky JS> Prohledávání doplneno konzistenCními technikami
A in 1..2, B in 0..1, B #< A it po provedení A #=1      se z B #< A se odvodí:      B #= 0
& Podmínky jako výstup
it kompaktní reprezentace nekoneCného poCtu r ešení, výstup lze použít jako vstup it dotaz: A in 0..2, B in 0..2, B #< A výstup: A in 1..2, B in 0..1,
Hana Rudová, Logické programování I, 26. dubna 2011 13 Logické programování s omezujícími podmínkami
Od LP k CLP II.
& Pro r ešení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
ii> Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky JS> Prohledávání doplneno konzistenCními technikami
A in 1..2, B in 0..1, B #< A -fc po provedení A #=1      se z B #< A se odvodí:      B #= 0
& Podmínky jako výstup
kompaktní reprezentace nekonecného poctu r ešení, výstup lze použít jako vstup A dotaz: A in 0..2, B in 0..2, B #< A výstup: A in 1..2, B in 0..1, B #< A
Hana Rudová, Logické programování I, 26. dubna 2011 13 Logické programování s omezujícími podmínkami
Syntaxe CLP
Výber jazyka omezení CLP klauzule
jako LP klauzule, ale její telo může obsahovat omezení daného jazyka
p(X,Y)       X #< Y+1, q(X), r(X,Y,Z).
Rezolucní krok v LP
a kontrola existence nejobecnejšího unifikátoru (MGU) mezi cílem a hlavou
£ Krok odvození v CLP také zahrnuje
S kontrola konzistence aktuální množiny omezení s omezeními v tele klauzule
=> Vyvolání dvou rešiců: unifikace + rešic omezení
Hana Rudová, Logické programování I, 26. dubna 2011
14
Logické programování s omezujícími podmínkami
Operační sémantika CLP
CLP výpocet cíle G
J» Store množina aktivních omezení = prostor omezení (constraint store) s» inicializace Store = 0
Jr seznamy cílů v G provádeny v obvyklém poradí a pokud narazíme na cíl s omezením c: NewStore = Store u {c} %> snažíme se splnit c vyvoláním jeho rešice pri neúspechu se vyvolá backtracking
pri úspechu se podmínky v NewStore zjednoduší propagací omezení &> zbývající cíle jsou provádeny s upraveným NewStore
CLP výpocet cíle G je úspešný, pokud se dostaneme z iniciálního stavu {G, 0) do stavu {G',Store), kde G je prázdný cíl a Store je splnitelná.
Hana Rudová, Logické programování I, 26. dubna 2011
15
Logické programování s omezujícími podmínkami
CLPCFD) v SICStus Prologu
Systémy a jazyky pro CP
J* IBM ILOG CP 1987
Jt omezující podmínky v C++, Jave nebo generickém modelovacím jazyků OPL iľ implementace podmínek založena na objektove orientovaném programování Jt špickový komercní sw, vznikl ve Francii, nedávno zakoůpen IBM J> nyní nove volne dostůpný pro akademické poůžití
Hana Růdová, Logické programování I, 26. důbna 2011
17
CLP(FD) v SICStůs Prologů
Systémy a jazyky pro CP
Ji* IBM ILOG CP 1987
it omezující podmínky v C++, Jave nebo generickém modelovacím jazyku OPL
it implementace podmínek založena na objektove orientovaném programování
it špickový komercní sw, vznikl ve Francii, nedávno zakoupen IBM
it nyní nove volne dostupný pro akademické použití
& Swedish Institute of Computer Science: SICStus Prolog 1985
it silná CLPCFD) knihovna, komercní i akademické použití
Hana Rudová, Logické programování I, 26. dubna 2011
17
CLPCFD) v SICStus Prologu
Systémy a jazyky pro CP
Ji* IBM ILOG CP 1987
a omezující podmínky v C++, Jave nebo generickém modelovacím jazyku OPL iľ implementace podmínek založena na objektove orientovaném programování a špickový komercní sw, vznikl ve Francii, nedávno zakoupen IBM j* nyní nove volne dostupný pro akademické použití
& Swedish Institute of Computer Science: SICStus Prolog 1985
-fc silná CLP(FD) knihovna, komercní i akademické použití
IC-PARC, Imperial College London, Cisco Systems: ECL*PSe 1984
& široké možnosti kooperace mezi různými rešicemi: konecné domény, reálná císla, repair
Jť od 2004 vlastní Cisco Systems volne dostupné pro akademické použití, rozvoj na IC-PARC, platformy: Windows, Linux, Solaris
Hana Rudová, Logické programování I, 26. dubna 2011
17
CLP(FD) v SICStus Prologu
Systémy a jazyky pro CP
Ji* IBM ILOG CP 1987
it omezující podmínky v C++, Jave nebo generickém modelovacím jazyku OPL
it implementace podmínek založena na objektove orientovaném programování
it špickový komercní sw, vznikl ve Francii, nedávno zakoupen IBM
it nyní nove volne dostupný pro akademické použití
& Swedish Institute of Computer Science: SICStus Prolog 1985
it silná CLP(FL)) knihovna, komercní i akademické použití
IC-PARC, Imperial College London, Cisco Systems: ECL*PSe 1984
it široké možnosti kooperace mezi různými rešicemi: konecné domény, reálná císla, repair
Jt od 2004 vlastní Cisco Systems volne dostupné pro akademické použití, rozvoj na IC-PARC, platformy: Windows, Linux, Solaris
ií> Mnoho dalších systému: Choco, Gecode, Minion, Oz, SWI Prolog, ...
Hana Rudová, Logické programování I, 26. dubna 2011 17 CLP(FD) v SICStus Prologu
CLPCFD) v SICStus Prologu
& Vestavené predikáty jsou dostupné v separátním modulu (knihovne) :- use_modu1e(1ibrary(c1pfd)).
Obecné principy platné všude nicméne standarty jsou nedostatecné
a stejné/podobné vestavené predikáty existují i jinde s CLP knihovny v SWI Prologu i ECLiPSe se liší
Hana Rudová, Logické programování I, 26. dubna 2011
18
CLP(FD) v SICStus Prologu
Príslušnost k doméne: Range termy
-i* ?- domain( [A,B], 1,3). domain( +Variables, +Min, +Max)
A in 1..3 B in 1..3
Hana Rudová, Logické programování I, 26. dubna 2011
19
CLPCFD) v SICStus Prologu
Príslušnost k doméne: Range termy
i& ?- domain( [A,B], 1,3). domain( +Variables, +Min, +Max)
A in 1..3 B in 1..3
Jfc ?- A in 1..8, A #\= 4. ?X in +Min..+Max
A in (1..3) \/ (5..8)
Hana Rudová, Logické programování I, 26. dubna 2011
19
CLP(FD) v SICStus Prologu
Príslušnost k doméne: Range termy
-i* ?- domain( [A,B], 1,3). domain( +Variab1es, +Min, +Max)
A in 1..3 B in 1..3
Jfc ?- A in 1..8, A #\= 4. ?X in +Min..+Max
A in (1..3) \/ (5..8)
& Doména reprezentována jako posloupnost intervalů celých ccísel
M ?- a in (1..3) \/ (8..15) \/ C5..9) \/ {100}. ?X in +Range
A in (1..3) \/ (5..15) \/ {100}
Hana Rudová, Logické programování I, 26. dubna 2011
19
CLP(FD) v SICStus Prologu
Príslušnost k doméne: Range termy
-i* ?- domain( [A,B], 1,3). domain( +Variab1es, +Min, +Max)
A in 1..3 B in 1..3
Jfc ?- A in 1..8, A #\= 4. ?X in +Min..+Max
A in (1..3) \/ (5..8)
& Doména reprezentována jako posloupnost intervalů celých císel
M ?- a in (1..3) \/ (8..15) \/ C5..9) \/ {100}. ?X in +Range
A in (1..3) \/ (5..15) \/ {100}
Zjištení domény Range promenné Var: fd_dom(?Var,?Range)
A in 1..8, A #\= 4, fd_dom(A,Range). Range=(1..3) \/ (5..8)
Hana Rudová, Logické programování I, 26. dubna 2011
19
CLP(FD) v SICStus Prologu
Príslušnost k doméne: Range termy
-i* ?- domain( [A,B], 1,3). domain( +Variables, +Min, +Max)
A in 1..3 B in 1..3
Jfc ?- A in 1..8, A #\= 4. ?X in +Min..+Max
A in (1..3) \/ (5..8)
& Doména reprezentována jako posloupnost intervalů celých Čísel
M ?- a in (1..3) \/ (8..15) \/ (5..9) \/ {100}. ?X in +Range
A in (1..3) \/ (5..15) \/ {100}
Zjištení domény Range promenné Var: fd_dom(?Var,?Range)
A in 1..8, A #\= 4, fd_dom(A,Range). Range=(1..3) \/ (5..8)
M A in 2..10, fd_dom(A,(1..3) \/ (5..8)). no
Hana Rudová, Logické programování I, 26. dubna 2011
19
CLP(FD) v SICStus Prologu
Příslušnost k doméne: Range termy
-i* ?- domain( [A,B], 1,3). domain( +Variab1es, +Min, +Max)
A in 1..3 B in 1..3
?- A in 1..8, A #\= 4. ?X in +Min..+Max
A in (1..3) \/ (5..8)
& Doména reprezentována jako posloupnost intervalů celých císel
M ?- a in (1..3) \/ (8..15) \/ C5..9) \/ {100}. ?X in +Range
A in (1..3) \/ (5..15) \/ {100}
Zjištení domény Range promenné Var: fd_dom(?Var,?Range)
A in 1..8, A #\= 4, fd_dom(A,Range). Range=(1..3) \/ (5..8)
A in 2..10, fd_dom(A,(1..3) \/ (5..8)). no
& Range term: reprezentace nezávislá na implementaci
Hana Rudová, Logické programování I, 26. dubna 2011
19
CLPCFD) v SICStus Prologu
P r íslušnost k doméne: FDSet termy
C FDSet term: reprezentace závislá na implementaci
J ?- A in 1..8, A#\= 4, fd_set(A,FDSet). A in (1..3) \/ (5..8) FDSet = [[1|3],[5|8]]
fd_set(?Var,?FDSet)
Hana Rudová, Logické programování I, 26. dubna 2011
20
CLP(FD) v SICStus Prologu
Príslušnost k doméne: FDSet termy
C FDSet term: reprezentace závislá na implementaci
M ?- A in 1..8, A #\= 4, fd_set(A,FDSet). fd_set(?Var,?FDSet) A in (1..3) \/ C5..8) FDSet = [[1|3],[5|8]]
J ?- A in 1..8.A #\= 4, fd_set(A,FDSet),B in_set FDSet.      ?X in_set +FDSet A in (1..3) \/ C5..8) FDSet = [[1|3],[5|8]] B in (1..3) \/ C5..8)
Hana Rudová, Logické programování I, 26. dubna 2011
20
CLP(FD) v SICStus Prologu
Příslušnost k doméne: FDSet termy
C FDSet term: reprezentace závislá na implementaci
M ?- A in 1..8, A #\= 4, fd_set(A,FDSet). fd_set(?Var,?FDSet) A in (1..3) \/ C5..8) FDSet = [[1|3],[5|8]]
J ?- A in 1..8.A #\= 4, fd_set(A,FDSet),B in_set FDSet.      ?X in_set +FDSet A in (1..3) \/ C5..8) FDSet = [[1|3],[5|8]] B in (1..3) \/ C5..8)
& FDSet termy predstavůjí nízko-úrovnovoů implementaci
FDSet termy nedoporůceny v programech
Jt poůžívat poůze predikáty pro manipůlaci s nimi -i- omezit poůžití A in_set [[1|2],[6|9]]
JS> Range termy preferovány
Hana Růdová, Logické programování I, 26. důbna 2011 20 CLP(FD) v SICStůs Prologů
Další fd_... predikáty
fdset_to_1ist(+FDset, -List) vrací do seznamu prvky FDset 1ist_to_fdset(+List, -FDset) vrací FDset odpovídající seznamu
fd_var(?Var)   je Var doménová promenná?
fd_min(?Var,?Min)    nejmenší hodnota v doméne fd_max(?Var,?Max)    nejvetší hodnota v doméne
fd_size(?Var,?Size)   velikost domény
fd_degree(?Var,?Degree) pocet navázaných omezení na promenné iľ mení se behem výpoctu: pouze aktivní omezení, i odvozená aktivní omezení
Hana Rudová, Logické programování I, 26. dubna 2011 21 CLP(FD) v SICStus Prologu
Aritmetická omezení
J* Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>=
a A + B #=< 3, A #\= (C - 4) * (D - 5), A/2 #= 4
a POZOR: neplést #=< a #>= s operátory pro implikaci:   #<= #=>
Hana Rudová, Logické programování I, 26. dubna 2011
22
CLP(FD) v SICStus Prologu
Aritmetická omezení
J* Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>=
a A + B #=< 3, A #\= (C - 4) * (D - 5), A/2 #= 4
a POZOR: neplést #=< a #>= s operátory pro implikaci:   #<= #=>
& sum(Van"ables,RelOp,Suma)
domain([A,B,C,F],1,3), sum([A,B,C],#= ,F) S> Variables i Suma musí být doménové proměnné nebo celá Čísla
Hana Rudová, Logické programování I, 26. dubna 2011
22
CLP(FD) v SICStus Prologu
Aritmetická omezení
J* Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>=
a A + B #=< 3, A #\= (C - 4) * (D - 5), A/2 #= 4
a POZOR: neplést #=< a #>= s operátory pro implikaci:   #<= #=>
& sum(Variab1es,Re1Op,Suma)
domain([A,B,C,F],1,3), sum([A,B,C],#= ,F) S> Variables i Suma musí být doménové promenné nebo celá císla
sca1ar_product(Coeffs,Variab1es,Re1Op,Sca1arProduct)
M domain([A,B,C,F],1,6), sca1ar_product( [1,2,3],[A,B,C],#= ,F)
iľ Variab1es i Va1ue musí být doménové promenné nebo celá císla, Coeffs jsou celá císla
j* POZOR na poradí argumentů, nejprve jsou celocíselné koeficienty, pak dom. promenné
3 sca1ar_product(Coeffs, Variab1es, #= , Va1ue, [consistency(domain)])
silnejší typ konzistence
POZOR: domény musí mít konecné hranice
Hana Rudová, Logické programování I, 26. dubna 2011 22 CLP(FD) v SICStus Prologu
Základní globální omezení
all_distinct(l_ist)
M všechny proměnné různé
cumulative(...)
disjunktivní a kumulativní rozvrhování
cumulatives(...)
kumulativní rozvrhování na více zdrojů
Hana Rudová, Logické programování I, 26. dubna 2011
23
CLP(FD) v SICStus Prologu
promenné různé
a11_distinct(Variab1es), a11_different(Variab1es)
ii> Promenné v seznamu Variab1es jsou různé
a11_distinct a a11_different se liší úrovní propagace
a a11_distinct má úplnou propagaci
a11_different má slabší (neúplnou) propagaci
Hana Rudová, Logické programování I, 26. dubna 2011
24
CLP(FD) v SICStus Prologu
Všechny proměnné různé
all_distinct(Variables), a11_different(Variab1es)
Proměnné v seznamu Variables jsou různé
a11_distinct a a11_different se liší úrovní propagace
a a11_distinct má úplnou propagaci
a a11_different má slabší (neúplnou) propagaci
Príklad: uCitelé musí uCit v mzné hodiny
uCitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
Hana Rudová, Logické programování I, 26. dubna 2011
24
CLP(FD) v SICStus Prologu
Všechny promenné různé
all_distinct(Variables), all_different(Variables)
Promenné v seznamu Variables jsou různé
all_distinct a all_different se liší úrovní propagace
a all_distinct má úplnou propagaci
a all_different má slabší (neúplnou) propagaci
Príklad: ucitelé musí ucit v mzné hodiny
all_distinct([Jan,Petr,Anna,Ota,Eva,Marie])
Jan = 6, Ota = 2, Anna = 5,
Marie = 1, Petr in 3..4, Eva in 3..4
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
Hana Rudová, Logické programování I, 26. dubna 2011
24
CLP(FD) v SICStus Prologu
Všechny promenné různé
a11_distinct(Variab1es), a11_different(Variab1es)
Promenné v seznamu Variab1es jsou různé
a11_distinct a a11_different se liší úrovní propagace
a a11_distinct má úplnou propagaci
a a11_different má slabší (neúplnou) propagaci
Príklad: ucitelé musí ucit v mzné hodiny
a11_distinct([Jan,Petr,Anna,Ota,Eva,Marie])
Jan = 6, Ota = 2, Anna = 5,
Marie = 1, Petr in 3..4, Eva in 3..4
3 a11_different([Jan,Petr,Anna,Ota,Eva,Marie]) Jan in 3..6, Petr in 3..4, Anna in 2..5, Ota in 2..4, Eva in 3..4, Marie in 1..6
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
Hana Rudová, Logické programování I, 26. dubna 2011
24
CLP(FD) v SICStus Prologu
Disjunktivní rozvrhování (unární zdroj)
-í* cumulative([task(Start, Duration, End, 1, Id) | Tasks])
-í* Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se neprekrývaly
Hana Rudová, Logické programování I, 26. dubna 2011
25
CLP(FD) v SICStus Prologu
Disjunktivní rozvrhování (unární zdroj)
-í* cumu1ative([task(Start, Duration, End, 1, Id) | Tasks])
-í* Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly
a príklad s konstantami: cumu1ative([task(0,2,2,1,1), task(3,1,4,1,2), task(5,1,6,1,3)])
					
	f.				3
1      2       3       4      5 6
Hana Rudová, Logické programování I, 26. dubna 2011
25
CLP(FD) v SICStus Prologu
Disjunktivní rozvrhování (unární zdroj)
-í* cumulative([task(Start, Duration, End, 1, Id) | Tasks])
-í* Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly
a príklad s konstantami: cumulative([task(0,2,2,1,1), task(3,1,4,1,2), task(5,1,6,1,3)])
					
	f. í		2		3
12       3       4      5 6
± príklad: vytvorení rozvrhu, za predpokladu, že doba trvání hodin není stejná
Hana Rudová, Logické programování I, 26. dubna 2011
25
CLP(FD) v SICStus Prologu
Disjunktivní rozvrhování (unární zdroj)
-í* cumulative([task(Start, Duration, End, 1, Id) | Tasks])
-í* Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly
it príklad s konstantami: cumulative([task(0,2,2,1,1), task(3,1,4,1,2), task(5,1,6,1,3)])
					
	f. í		2		3
12       3       4      5 ó
± příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná JanE#= Jan+1, PetrE#= Petr+1, AnnaE#= Anna+2,
cumulative(task(Jan,1,JanE,1,1),task(Petr,1,PetrE,1,2),task(Anna,1,AnnaE,1,3), task(Ota,2,OtaE,1,4),task(Eva,2,EvaE,1,5),task(Marie,3,MarieE,1,6)])
Hana Rudová, Logické programování I, 26. dubna 2011
25
CLP(FD) v SICStus Prologu
Kumulativní rozvrhování
& cumulative([task(Start,Duration,End,Demand,TaskId) | Tasks],
[limit(Limit)])
& Rozvržení úloh zadaných startovním a koncovým Časem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a identifikátorem (Id) tak, aby se nepřekrývaly a aby celková kapacita zdroje nikdy neprekrocila Limit
Hana Rudová, Logické programování I, 26. dubna 2011
26
CLP(FD) v SICStus Prologu
Kumulativní rozvrhování
& cumu1ative([task(Start,Duration,End,Demand,TaskId) | Tasks],
[limit(Limit)])
& Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a identifikátorem (Id) tak, aby se nepřekrývaly a aby celková kapacita zdroje nikdy neprekrocila Limit
ií> Príklad s konstantami:
cumu1ative([task(Q,4,4,1,1),task(1,2,3,2,2),task(3,3,6,2,3),task(4,2,6,1,4)],[1imit(3)])
	2		4
			3
1			
T
Hana Rudová, Logické programování I, 26. dubna 20111 ^   26   ^ ^ ° u CLP(FD) v SICStus Prologu
Kumulativní rozvrhování s více zdroji
Rozvržení úloh tak, aby se nepřekrývaly a daná kapacita zdrojů nebyla překročena (limit zdroje chápán jako horní mez - bound(upper))
cumu1atives([task(Start,Duration,End,Demand,MachineId)|Tasks],
[machine(Id,Lirrrit)|Machines] ,[bound(upper)])
Úlohy zadány startovním a koncovým časem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a požadovaným typem zdroje (Machineld)
Zdroje zadány identifikátorem (Id) a kapacitou (Limit)
Hana Rudová, Logické programování I, 26. dubna 2011
27
CLP(FD) v SICStus Prologu
Kumulativní rozvrhování s více zdroji
i& Rozvržení úloh tak, aby se neprekrývaly a daná kapacita zdrojů nebyla prekrocena (limit zdroje chápán jako horní mez - bound(upper))
iS> cumulatives([task(Start,Duration,End,Demand, MachineId)|Tasks],
[machine(Id,Limit)|Machines],[bound(upper)])
& Úlohy zadány startovním a koncovým ccasem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a požadovaným typem zdroje (MachineId)
& Zdroje zadány identifikátorem (Id) a kapacitou (Limit)
M Príklad:
?- domain([B,C],1,2),
cumulatives([task(0,4,4,1,1),task(3,1,4,1,B), task(5,1,6,1,C)],
[machine(1,1),machine(2,1)],
[bound(upper)]). C in 1..2, B=2
Hana Rudová, Logické programování I, 26. dubna 2011 27 CLP(FD) v SICStus Prologu