CP: elektronické materiály Logické programování s omezujícími podmínkami Constraint Logic Programming: CLP Dechter, R. Constraint Processing. Morgan Kaufmann Publishers, 2003. ■ http://www.ics.uci.edu/~dechter/books/ Barták R. Přednáška Omezující podmínky na MFF UK, Praha. ■ http://kti.ms.mff.cuni.cz/~bartak/podminky/prednaska.html SICStus Prolog User's Manual, 2007. Kapitola o CLP(FD). ■ http://www.fi.muni.cz/~hanka/sicstus/doc/html/ Příklady v distribuci SICStus Prologu: cca 45 příkladů, zdrojový kód ■li b/sicstus-'-'-'/T i brary/cl pfd/examples/ Probírané oblasti ■ Obsah ■ úvod: od LP k CLP ■ základy programování ■ základní algoritmy pro řešení problémů s omezujícími podmínkami ■ Příbuzné přednášky na Fl ■ PA163 Programování s omezujícími podmínkami ■ http://www.fi.muni.cz/~hanka/cp ■ PA1 67 Rozvrhování ■ http://www.fi.muni.cz/~hanka/rozvrhováni ■ zahrnuty CP techniky pro řešení rozvrhovacích problémů Hana Rudová, Logické programování I, 6. května 2010 2 Logické programování s omezujícími podmínkami Historie a současnost ■ 1963 interaktivní grafika (Sutherland: Sketchpad) ■ Polovina 80. let: logické programování omezujícími podmínkami ■ Od 1990: komerční využití ■ Už v roce 1996: výnos řádově stovky milionů dolarů ■ Aplikace - příklady ■ Lufthansa: krátkodobé personální plánování ■ reakce na změny při dopravě (zpoždění letadla, ...) ■ minimalizace změny v rozvrhu, minimalizace ceny ■ Nokia: automatická konfigurace sw pro mobilní telefony ■ Renault: krátkodobé plánování výroby, funkční od roku 1995 Hana Rudová, Logické programování I, 6. května 2010 3 Logické programování s omezujícími podmínkami Hana Rudová, Logické programování I, 6. května 2010 4 Logické programování s omezujícími podmínkami ,Vfc} Dk} Omezení (constraint) Dána ■ množina (doménových) proměnných Y = {yi ■ konečná množina hodnot (doména) D = {Di,. Omezení c na Y je podmnožina D\ x ... x Dk ■ omezuje hodnoty, kterých mohou proměnné nabývat současně Příklad: ■ proměnné: A,B ■domény: {0,1} pro A {1,2} pro B ■omezení: A^B nebo (A,B) e {(0,1 ),(0,2),(1,2)} Omezení c definováno na y\,.. .yt je splněno, pokud pro d\ e D\,.. .dk e Dk platí (tři, ■ ■ ■ dk) e c ■ příklad (pokračování): omezení splněno pro (0,1), (0,2), (1, 2), není splněno pro (1,1) Hana Rudová, Logické programování I, 6. května 2010 Logické programování s omezujícími podmínkami Řešení CSP Částečné ohodnocení proměnných (d\,dk),k < n ■ některé proměnné mají přiřazenu hodnotu Úplné ohodnocení proměnných (d\,..., dn) ■ všechny proměnné mají přiřazenu hodnotu Řešení CSP ■ úplné ohodnocení proměnných, které splňuje všechna omezení ■ (tři, ■ ■ ■, d„) e Di x ... x Dn je řešení (X, D, C) ■ pro každé cf e C na X{v .. platí (d\l,.. .dik) e cf Hledáme: jedno nebo všechna řešení nebo optimální řešení (vzhledem k objektivní funkci) Hana Rudová, Logické programování I, 6. května 2010 Logické programování s omezujícími podmínkami Problém splňování podmínek (CSP) Dána ■ konečná množina proměnných X = {xi,...,x„} ■ konečná množina hodnot (doména) D = {D\,...,Dn} ■ konečná množina omezení C = {C\.....cm} ■ omezení je definováno na podmnožině X Problém splňování podmínek je trojice (X,D,C) (constraint satisfaction problem) Příklad: ■ proměnné: A,B,C ■domény: {0,1} pro A {1,2} pro B {0,2} pro C ■ omezení: A^B, B^C Hana Rudová, Logické programování I, 6. května 201 0 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í: al 1_di sti nct( [Jan, Petr, . . . ]) částečné ohodnocení: Jan=6, Anna=5, Marie=l úplné ohodnocení: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=6 řešení CSP: 3an=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=l všechna řešení: ještě Jan=6, Petr=4, Anna=5, 0ta=2, Eva=3, Marie=l optimalizace: ženy učí co nejdříve Anna+Eva+Marie #= Cena minimalizace hodnoty proměnné Cena optimální řešení: Jan=6, Petr=4, Anna=5, 0ta=2, Eva=3, Marie=l 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, 6. května 2010 Logické programování s omezujícími podmínkami CLPCFD) program Kód CLPCFD) programu Základní struktura CLP programu 1. definice proměnných a jejich domén 2. definice omezení 3. hledání řešení (1) a (2) deklarativní část ■ modelování problému ■ vyjádření problému splňování podmínek (3) řídící část ■ prohledávání stavového prostoru řešení ■ procedura pro hledání řešení (enumeraci) se nazývá labeling ■ umožní nalézt jedno, všechna nebo optimální řešení Hana Rudová, Logické programování I, 6. května 2010 9 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 a M nejsou 0 domain([E,N,D,0,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_distinctC [S,E,N,D,M,0,R,Y] ) labelingC [5,E,N,D,M,0,R,Y] ) Hana Rudová, Logické programovaní I, 6. května 2010 11 Logické programováni s omezujícími podmínkami % základní struktura CLP programu solveC Variables ) :- declare_variablesC Variables ), domainCpan] ,3,6], ... post_constraints( Variables ), an_distinct([jan,Petr,...]) labelingC Variables ). % triviální labeling labelingC [] ). labelingC [Var|Rest] ) :- fd_minCVar,Min) , % výběr nejmenší hodnoty z domény C Var#=Min, labelingC Rest ) i Var#>Min , labelingC [Var|Rest] ) Hana Rudova, Logické programování I, 6. května 2010 10 Logické programování s omezujícími podmínkami Od LP k CLP I. ■ CLP: rozšíření logického programování o omezující podmínky ■ CLP systémy se liší podle typu domény ■ CLP(JZI) generický jazyk ■ CLP(FD) domény proměnných jsou konečné (Finite Domains) ■ CLP(R) doménou proměnných je množina reálných čísel ■ Cíl ■ využít syntaktické a výrazové přednosti LP ■ dosáhnout větší efektivity ■ Unifikace v LP je nahrazena splňováním podmínek ■ unifikace se chápe jako jedna z podmínek ■ A = B ■ A #< B, A in 0..9, domain([A,B] ,0,9), a"l"l_di sti net ([A, B, C]) Hana Rudová, Logické programování I, 6. května 201 0 1 2 Logické programováni s omezujícími podmínkami Od LP k CLP II. Syntaxe CLP ■ Pro řešení podmínek se používají konzistenční techniky ■ 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 ■ Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky ■ Prohledávání doplněno konzistenčními technikami ■A in 1..2, B in 0..1, B# Vyvolání dvou řešičů: unifikace + řešič omezení Hana Rudová, Logické programování I, 6. května 2010 14 Logické programování s omezujícími podmínkami Operační sémantika CLP CLP výpočet cíle G ■ Store množina aktivních omezení = prostor omezení (constraint store) ■ inicializace Store = 0 ■ seznamy cílů v G prováděny v obvyklém pořadí ■ pokud narazíme na cíl s omezením c: NewStore = Store u {c} ■ snažíme se splnit c vyvoláním jeho řešiče ■ při neúspěchu se vyvolá backtracking ■ při úspěchu se podmínky v NewStore zjednoduší propagací omezení ■ zbývající cíle jsou prováděny s upraveným NewStore CLP(FD) v SICStus Prologu CLP výpočet cíle G je úspěšný, pokud se dostaneme z iniciálního stavu (G, 0} do stavu #= | #\= | #< | #=< | #> | #>= ■ A + B #=< 3, A #\= (C - 4) * C D - 5), A/2 #= 4 ■ POZOR: neplést #=< a #>= s operátory pro implikaci: #<= #=> ■ sum(Variables,RelOp,Suma) ■ domain([A,B,C,F],1,3), sum([A,B,C],#= ,F) ■ Variables i Suma musí být doménové proměnné nebo celá čísla ■ scalar_product(Coeffs,Variables,RelOp,Seal arProduct) ■ domain([A,B,C,F],1,6), scalar_product( [1,2,3],[A,B,C],#= ,F) ■ Variables i Val ue musí být doménové proměnné nebo konstanty, Coeff s jsou celá čísla ■ POZOR na pořadí argumentů, nejprve jsou celočíselné koeficienty, pak dom. proměnné ■ scalar_product(Coeffs, Variables, #= , Value, [consistency(domain)]) ■ silnější typ konzistence ■ POZOR: domény musí mít konečné hranice Hana Rudová, Logické programování I, 6. května 2010 22 CLP(f D) v SICStus Prologu Výroková omezení, reifikace Výroková omezení pozor na efektivitu ■ \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence,... ■ X #> 4 #/\ Y #< 6 ■ příklad: A#\= 3, A#\= 4 A#\= 3 #/\ A#\= 4 A#=l #\/ A#=2 A in (inf..2)\/ (5..sup) A in (inf..2)\/ (5..sup) A in inf..sup tj. propagace disjunkce A#=l #\/ A#=2 je příliš slabá (propagační algoritmy příliš obecné) Reifikace pozor na efektivitu ■ Constraint #<=> Bool Bool in 0.. 1 v závislosti na tom, zda je Constrai nt splněn ■ příklad: A in 1..10 #<=> Bool ■ za předpokladu X in 3.. 10, Y in 1..4, Bool in 0..1 porovnej rozdíl mezi X# Bool X = 3, Y = 4 X in 3..10, Y in 1..4, Bool in 0..1 Hana Rudová, Logické programování I, 6. května 2010 23 CLP(fD) v SICStus Prologu Příklad: reifikace ■ Přesně N prvků v seznamu S je rovno X: exactly (X, S, N) exactlyC [], 0). exactly(X, [Y|L], N) :- X #= Y #<=> B, % reifikace N #= M+B, % doménová proměnná místo akumulátoru exactly(X, L, M). ■ | ?- domain([A,B,C,D,E,N],1,2), exactly(1,[A,B,C,D,E],N),A#< 2,B#< 2. A = 1, B = 1, C=2, D=2, E=2, N=2 ■ Vyzkoušejte si ■ greaters(X,S,N): přesně N prvků v seznamu S je větší než X ■ atleastCX, S, N): alespoň N prvků v seznamu S je rovno X ■ atmost(X,S,N): nejvýše N prvků v seznamu S je rovno X Hana Rudová, Logické programování I, 6. května 2010 24 CLP(f D) v SICStus Prologu Základní globální omezení Všechny proměnné různé a"l"l_ch'stinct(List) ■ všechny proměnné různé cumulative(...), cumulatives(...) ■ disjunktivní a kumulativní rozvrhování a"l"l_di sti nct (Vari abl es), a"l"l_di f f e rent (Vari abl es) Proměnné v seznamu Variables jsou různé a"l"l_distinct a a"l"l_di fferent se liší úrovní propagace ■ a"l"l_distinct má úplnou propagaci ■ a"l"l_di fferent má slabší (neúplnou) propagaci Příklad: učitelé musí učit v různé hodiny ■ all_di sti nctC[Jan,Petr,Anna,Ota,Eva,Marie]) Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr in 3..4, Eva in 3..4 ■ all_differentC[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, 6. května 2010 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 časem (Start, End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly ■ příklad s konstantami: cumulative([task(0,2,2,l ,1), task(3,l ,4,1,2), task(5,l ,6,1,3)]) 1 2 3 1 1 2 3 4 5 6 ■ 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, task(0ta,2,OtaE,1,4),task(Eva,2,EvaE,1,5),task(Mari e,3,Mari eE,1,6) ]) Hana Rudová, Logické programování I, 6. května 2010 27 CLP(fD) v SICStus Prologu Hana Rudová, Logické programování I, 6. května 2010 26 CLP(fD) v SICStus Prolog Kumulativní rozvrhování ■ cumulative([task(Start,Duration,End,Demand,TaskId) | Tasks], [li mi t (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 nepřekročila Limit ■ Příklad s konstantami: cumulative([task(0,4,4,l,l),task(l,2,3,2,2),task(3,3,6,2,3),task(4,2,6,l,4)],[limit(3)]) 2 3 1 1 1 1 1 1 2 3 4 5 6 Hana Rudová, Logické programování I, 6. května 2010 28 CLP(fD) v SICStus Prolog 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)) cumulatives([tas k(Start,Duration,End,Demand,Machi neld)|Tasks], [machi ne(Id,Limit)|Machi nes],[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 (Machi neld) Zdroje zadány identifikátorem (Id) a kapacitou (Limit) Příklad: ?- domain([B,C],1,2), cumulatives([task(0,4,4,l,l),task(3,1,4,1,B), task(5,l,6,l,C)] [machine(l,l),machine(2,1)], [bound(upper)]). C in 1..2, B=2 Hana Rudová, Logické programování 1,6. května 2010 29 CLP(f D) v SICStus Prologu