Logické programování s omezujícími podmínkami Constraint Logic Programming: CLP 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ů CP: elektronické materiály ■ 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 Manuál, 2004. Kapitola o CLP(FD). ■ http://www.fi.muni.cz/~hanka/sicstus/doc/html/ ■ Příklady v distribuci SICStus Prologu: cca 25 příkladů, zdrojový kód ■ ai sa:/software/sicstus-3.10.1/1 i b/sicstus-3.10.l/li brary/clpfd/examples/ ■ Constraint Programming Online ■ http://slash.math.uni pd.it/cp/i ndex.php Hana Rudová, Logické programování I, 17. dubna 2009 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, 17. dubna 2009 3 Logické programování s omezujícími podmínkami Hana Rudová, Logické programování I, 17. dubna 2009 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, 17. dubna 2009 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, 1 7. dubna 2009 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, 1 7. dubna 2009 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, 1 7. dubna 2009 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, 17. dubna 2009 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, 1 7. dubna 2009 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, 1 7. dubna 2009 1 0 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, 1 7. dubna 2009 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, 17. dubna 2009 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 #= I #\= I #< I #=< I #> I #>= ■ A + B #=< 3, A #\= (C - 4) * C D - 5), A/2 #= 4 ■ sum(Variables,RelOp,Suma) ■ domai n C[A,B,C,F],1,3), sum([A,B,C],#= ,F) ■ scalar_product(Coeffs.Variables,RelOp,Seal arProduct) ■ domai n C[A,B,C,F],1,6), scalar_product( [1,2,3],[A,B,C],#= ,F) Hana Rudová, Logické programování I, 1 7. dubna 2009 CLP(fD>vSICStus Prologu Výroková omezení, reifikace Výroková omezení pozor na efektivitu \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence,... X #> 4 #/\ Y #< 6 za předpokladu A in 1..4: 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, 1 7. dubna 2009 CLP(fD>vSICStus Prologu Hana Rudová, Logické programování I, 1 7. dubna 2009 CLP(fD>vSICStus 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, N #= M+B, exactly(X, L, M). % reifikace % doménová proměnná místo akumulátoru ■ I ?- 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 ■ at leas t (X, 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, 17. dubna 2009 CLP(fD)vSICStus Prologu Základní kombinatorická omezení ■ element(N,List,X) ■ omezení na konkrétní prvek seznamu ■ global_cardinality(Li st, [Key-Count | _ ]) ■ omezení na počet prvků daného typu v seznamu ■ a"l"l_distinct(List) ■ všechny proměnné různé ■ seri ali zed(Starts,Du rati ons) ■ disjunktivní rozvrhování ■ disjoint2(Rectangles) ■ nepřekrývání obdélníků ■ cumulati ve(Starts,Durations,Resources,Limit) ■ kumulativní rozvrhování Hana Rudová, Logické programování I, 17. dubna 2009 25 CLP(fD) v SICStus Prologu Výskyty prvků v seznamu ■ element(N,List,X) ■ N-tý prvek v seznamu Li st je roven X ■ | ?- A in 2..10, B in 1..3, element( N, [A,B], X ), X#< 2. B = l,N = 2,X=l,Ain 2..10 ■ global_cardinality(List, KeyCounts) ■ pro každý prvek Key-Count seznamu KeyCounts platí: Count prvků seznamu List se rovná klíči Key ■ každé Key je celé číslo a vyskytuje se mezi klíči maximálně jednou ■ global_cardinality(S, [X-N] ) je obdobné omezení exactly(X,S,N) ■ | ?- A in 1..3, B in 1..3, global_cardinality( [A,B], [l-N.2-2]). A=2, B=2, N=0 Hana Rudová, Logické programování I, 17. dubna 2009 26 CLP(fD) v SICStus Prologu Příklad: rozvrhování zaměstnanců vytvoření rozvrhu pro zaměstnance pracující na směny ■A = {R,D,N,Z,V} = {1,2,3,4,5} Po Út St Čt ráno, den, noc, záloha, volno Petr R N v R Pavel R Z R N ■ P = {Petr,Pavel.Marie,...} Marie N v D D ■ W = {Po,Út,St,Čt,...} matice doménových proměnných: PetrPo, PetrUt, . . . , Pavel Po, . . . každý den: minimální a maximální počet zaměstnanců každou směnu Rl in MinRanol..MaxRanol, Dl in MinDenl..MaxDenl, ... global_cardinality( [PetrPo,Pavel Po.MariePo,...], [1-R1.2-D1.....5-V1] ) pro každého zaměstnance: minimální a maximální počet typu směny za týden R2 in MinRano2..MaxRano2, D2 in MinDen2..MaxDen2, ... global_cardinality( [PetrPo,PetrUt.....PetrNe], [1-R2.2-D2 Hana Rudová, Logické programování I, 17. dubna 2009 ,5-V2] ) CLPCfD) v SICStus Prologu Všechny proměnné různé all_distinct(Variables), all_different(Variables) Proměnné v seznamu Variables jsou různé all_distinct a all_different se liší úrovní propagace ■ all_distinct má úplnou propagaci ■ all_different 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_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, 1 7. dubna 2009 CLP(FD) v SICStus Prologu Disjunktivní rozvrhování Nepřekrývání obdélníků seri ali zed(Starts,Du rati ons) Rozvržení úloh zadaných startovním časem (seznam Starts) a dobou trvání (seznam nezáporných Du rati ons) tak, aby se nepřekrývaly ■ příklad s konstantami: serialized([0,3,5],[2,l ,1]) 3 1 -1- 1 2 3 4 5 6 příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná ■ D in 1..2, C = 3, seriálizedC pan,Petr,Anna,Ota,Eva,Marie], [D,D,D,C,C,C]) Hana Rudová, Logické programování I, 17. dubna 2009 CLP(fD) v SICStus Prologu Kumulativní rozvrhování cumulative(Starts,Durations,Resources,Limit) Úlohyjsou zadány startovním časem (seznam Starts), dobou trvání (seznam Durations) a požadovanou kapacitou zdroje (seznam Resources) Rozvržení úloh tak, aby celková kapacita zdroje nikdy nepřekročila Limit Příklad s konstantami: cumulative([0,l ,3],[4,2,3],[1,2,2],3) 3 Hana Rudová, Logické programování I, 17. dubna 2009 CLP(fD) v SICStus Prologu di sjoi nt2(Rectangles) disjoint2( [Name(X, Délka, Y, Vyska) di sjoi ntl(Li nes) ] ) umístění obdélníků ve dvourozměrném prostoru doménové proměnné X,Y,Délka,Vyska mohou být z oboru celých čísel ■ příklad s konstantami: disjoint2([rect(0,3,0,l),rect(l,3,1,2),rect(4,2,2,-2)]) 1 2 3 4 5 6 ■ příklad: vytvoření rozvrhu za předpokladu, že učitelé učí v různých místnostech D in 1..2, C = 3, disjoint2( classQan,D,Ml,l), class(Petr,D,M2,1), class(Petr,D,M3,1), ...] Hana Rudová, Logické programování I, 17. dubna 2009 30 CLP(fD) v SICStus Prologu Příklad: kumulativní rozvrhování Vytvořte rozvrh pro následující úlohy, tak aby nebyla překročena kapacita 1 3 zdroje, a minimalizujte celkovou dobu trvání úloha doba trvání kapacita tl 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 t7 4 11 18, 4], 1, 11], % koncový čas scheduleCSs, End) :-lengthCSs, 7), Ds = [16, 6, 13, 7, 5, Rs = [2, 9, 3, 7, 10, domainCSs, 0, 51), domain C [End] , 0, 69), afterCSs, Ds, End), cumulativeCSs, Ds, Rs, 13), appendCSs, [End], Vars), labeling([minimize(End)], Vars). after([], [], _) . after([S|Ss], [D|Ds], E) :- E #>= S+D, afterCSs, Ds, E) . I ?- scheduleCSs, End). Ss = Ss = [0,16,9,9,4,4,0], End = 22 ? Hana Rudová, Logické programování I, 1 7. dubna 2009 CLP(FD) v SICStus Prologu