Úvod do programování s omezujícími podmínkami Obsah přednášky Ukázkový příklad: sudoku Základní pojmy: omezení, ... Jak řešíme problémy s omezujícími podmínkami Příklady a aplikace Složitost a úplnost Hana Rudová, Omezující podmínky, 23. září 201 9 2 Úvod do CP Sudoku: problém 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Příklad převzat z přednášky Ch.Schulte, University of Uppsala Hana Rudová, Omezující podmínky, 23. září 2019 3 Úvod do CP Sudoku: řádky 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 4 Úvod do CP Sudoku: sloupce 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 5 Úvod do CP Sudoku: bloky 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 6 Úvod do CP Propagace v bloku: vstup 8 co 3 Hana Rudová, Omezující podmínky, 23. září 201 9 7 Úvod do CP Propagace v bloku: vstup 8 co 3 Žádné pole v bloku nemůže obsahovat čísla 3,6,8 Hana Rudová, Omezující podmínky, 23. září 201 9 7 Úvod do CP Propagace v bloku: promazání hodnot 1,2,4,5,7,9 8 1,2,4,5,7,9 1,2,4,5,7,9 6 3 1,2,4,5,7,9 1,2,4,5,7,9 1,2,4,5,7,9 M Žádné pole v bloku nemůže obsahovat čísla 3,6,8 M propagace do dalších polí v bloku 3 Řádky a sloupce: podobně Hana Rudová, Omezující podmínky, 23. září 2019 8 Úvod do CP Propagace: jedno pole 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 9 1,2,3,4,5,6,7,8,9 Úvod do CP Propagace: jedno pole a řádek 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 10 Úvod do CP Propagace: jedno pole a sloupec 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 Úvod do CP Propagace: jedno pole a blok 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 12 Úvod do CP Iterativní propagace 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Iterování propagací pro řádky, sloupce, bloky Pokud stále zůstává více možností: prohledávání Hana Rudová, Omezující podmínky, 23. září 2019 13 Úvod do CP Sudoku a programování s omezujícími podmínkami 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Proměnné: pro každé pole mají hodnoty: čísla udržování množiny možných čísel Omezení: vyjadřují odlišnosti ^ relace mezi proměnnými Modelování: proměnné, hodnoty, omezení Řešení: propagace, prohledávání Hana Rudová, Omezující podmínky, 23. září 201 9 14 Úvod do CP Omezení (constraint) 3 Dána množina (doménových) proměnných Y = {yi,... ,yk} 3 konečná množina hodnot (doména) D = D\ u ... u Dk Omezení (podmínka) c na Y je podmnožina D\ x ... x Dk tj. relace omezuje hodnoty, kterých mohou proměnné nabývat současně Hana Rudová, Omezující podmínky, 23. září 201 9 Úvod do CP Omezení (constraint) Dána množina (doménových) proměnných Y = {yi,... ,yk} 3 konečná množina hodnot (doména) D = D\ u ... u Dk Omezení (podmínka) c na Y je podmnožina D\ x ... x Dk tj. relace omezuje hodnoty, kterých mohou proměnné nabývat současně Příklad: 3 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)} Hana Rudová, Omezující podmínky, 23. září 201 9 Úvod do CP Omezení (constraint) 3 Dána množina (doménových) proměnných Y = {yi,... ,yk} 3 konečná množina hodnot (doména) D = D\ u ... u Dk Omezení (podmínka) c na Y je podmnožina D\ x ... x Dk tj. relace omezuje hodnoty, kterých mohou proměnné nabývat současně 3 Příklad: 3 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 proměnných yi,.. .yk je splněno, pokud pro hodnoty d\ e Di, ...dk £ Dk platí (d\,... dk) £ c M příklad (pokračování): omezení splněno pro (0,1), (0,2), (1, 2), není splněno pro (1,1) Hana Rudová, Omezující podmínky, 23. září 201 9 Úvod do CP Problém splňování podmínek (CSP) Dána M konečná množina proměnných X = {x\,..., xn} M konečná množina hodnot (doména) D = D\ u ... u D 3 konečná množina omezení C = {ci,..., cm} 3 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á, Omezující podmínky, 23. září 201 9 16 Úvod do CP Problém splňování podmínek (CSP) Dána M konečná množina proměnných X = {x\,..., xn} M konečná množina hodnot (doména) D = D\ u ... u D 3 konečná množina omezení C = {ci,..., cm} 3 omezení je definováno na podmnožině X Problém splňování podmínek je trojice (X,D,C) (constraint satisfaction problem) 3 Příklad: 3 proměnné: A,B, C -•domény: A e {0,1} B = l C e {0,1,2} M omezení: A =/= B B =/= C Hana Rudová, Omezující podmínky, 23. září 201 9 16 Úvod do CP Řešení CSP Částečné ohodnocení (přiřazení) proměnných (d\,dk),k < n M některé proměnné mají přiřazenu hodnotu Úplné ohodnocení (přiřazení) proměnných (d\,..., dn) M všechny proměnné mají přiřazenu hodnotu Hana Rudová, Omezující podmínky, 23. září 201 9 17 Úvod do CP Řešení CSP & Částečné ohodnocení (přiřazení) proměnných (d\,..., dk),k < n M některé proměnné mají přiřazenu hodnotu Úplné ohodnocení (přiřazení) proměnných (di,..., dn) 3 všechny proměnné mají přiřazenu hodnotu Řešení CSP úplné ohodnocení proměnných, které splňuje všechna omezení (di,...,dn) g Di x ... x Dn je řešení (X,D,C) ±> pro každé a e C na x^,.. .Xik platí (d^,... dik) e a Hana Rudová, Omezující podmínky, 23. září 201 9 17 Úvod do CP Řešení CSP M Částečné ohodnocení (přiřazení) proměnných (d\,dk),k < n M některé proměnné mají přiřazenu hodnotu & Úplné ohodnocení (přiřazení) proměnných (di,..., dn) M všechny proměnné mají přiřazenu hodnotu Řešení CSP 3 úplné ohodnocení proměnných, které splňuje všechna omezení (di,...,dn) g Di x ... x Dn je řešení (X,D,C) pro každé a g C na Xix,.. .Xik platí (d^,... dik) g a 3 Hledáme: jedno řešení nebo všechna řešení nebo optimální řešení vzhledem k účelové funkci, tj. řešíme optimalizační problém s podmínkami (constraint optimization problem) Hana Rudová, Omezující podmínky, 23. září 2019 17 Úvod do CP Přístup CP k programování Formulace daného problému pomocí omezení: modelování Řešení vybrané reprezentace pomocí M doménově specifických metod M obecných metod Hana Rudová, Omezující podmínky, 23. září 2019 18 Úvod do CP Obecné metody Algoritmy propagace omezení (konzistenční algoritmy) umožňují odstranit nekonzistentní hodnoty z domén proměnných M zjednodušují problém 3 udržují ekvivalenci mezi původním a zjednodušeným problémem 3 používají se pro výpočet lokální konzistence M aproximují tak globální konzistenci A e {0,1}, B = 1, C g {0,1,2}, A + B, A + C Hana Rudová, Omezující podmínky, 23. září 201 9 19 Úvod do CP Obecné metody Algoritmy propagace omezení (konzistenční algoritmy) umožňují odstranit nekonzistentní hodnoty z domén proměnných M zjednodušují problém 3 udržují ekvivalenci mezi původním a zjednodušeným problémem 3 používají se pro výpočet lokální konzistence M aproximují tak globální konzistenci A e {0,1}, B = 1, C g {0,1,2}, A + B, A + C po propagaci: A = 0, B = 1, C g {1,2} Hana Rudová, Omezující podmínky, 23. září 201 9 19 Úvod do CP Obecné metody Algoritmy propagace omezení (konzistenční algoritmy) umožňují odstranit nekonzistentní hodnoty z domén proměnných M zjednodušují problém 3 udržují ekvivalenci mezi původním a zjednodušeným problémem 3 používají se pro výpočet lokální konzistence 3 aproximují tak globální konzistenci A e {0,1}, B = 1, C g {0,1,2}, A + B, A + C po propagaci: A = 0, B = 1, C g {1,2} Prohledávací algoritmy 3 prohledávání stavového prostoru řešení příklady: backtracking, metoda větví a mezí Hana Rudová, Omezující podmínky, 23. září 201 9 19 Úvod do CP Prohledávání: příklad Prohledávání pomocí větvení vytvoření podproblému s dodatečnou informací umožní další propagaci omezení X: {4,5}, Y: {4,5} X >=Y X=4 XÉ4 X = 4, Y = 4 X >=Y X = 5, Y: {4,5} X >=Y Hana Rudová, Omezující podmínky, 23. září 201 9 20 Úvod do CP Doménově specifické metody Specializované algoritmy 3 Nazývány řešiče omezení (constraint solvers) 3 Příklady: program pro řešení systému lineárních rovnic 3 knihovny pro lineární programování 3 implementace unifikačního algoritmu Hana Rudová, Omezující podmínky, 23. září 201 9 21 Úvod do CP Doménově specifické metody Specializované algoritmy 3 Nazývány řešiče omezení (constraint solvers) 3 Příklady: program pro řešení systému lineárních rovnic 3 knihovny pro lineární programování M implementace unifikačního algoritmu Programování s omezujícími podmínkami 3 široký pojem zahrnující řadu oblastí M lineární algebra, globální optimalizace, lineární a celočíselné programování, ... M Existence doménově specifických metod => použití místo obecných metod hledání doménově specifických metod tak, aby mohly být použity místo obecných metod Hana Rudová, Omezující podmínky, 23. září 2019 21 Úvod do CP Algebrogram Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: 3 SEND + MORE MONEY M různá písmena mají přiřazena různé cifry M S a M nejsou 0 Jediné řešení: 9567 + 1085 10652 Proměnné: Hana Rudová, Omezující podmínky, 23. září 201 9 22 Úvod do CP Algebrogram Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: 3 SEND + MORE MONEY M různá písmena mají přiřazena různé cifry M S a M nejsou 0 Jediné řešení: 9567 + 1085 10652 3 Proměnné: S,E,N,D,M,O,R,Y 3 Domény: 1 ..9 pro S,M 0..9 pro E,N,D,0,R,Y Hana Rudová, Omezující podmínky, 23. září 2019 22 Úvod do CP Algebrogram: alternativy pro omezení rovnosti 1 omezení rovnosti Hana Rudová, Omezující podmínky, 23. září 201 9 23 Úvod do CP Algebrogram: alternativy pro omezení rovnosti 1 omezení rovnosti 1000*S + 100*E + 10*N + D SEND + 1000*M + 100*0 + 10*R + E + MORE = 10000*M + 1000*0 + 100*N + 10*E + Y MONEY Hana Rudová, Omezující podmínky, 23. září 201 9 23 Úvod do CP Algebrogram: alternativy pro omezení rovnosti 1 omezení rovnosti 1000*S + 100*E + 10*N + D SEND + 1000*M + 100*0 + 10*R + E + MORE = 10000*M + 1000*0 + 100*N + 10*E + Y MONEY 5 omezení rovnosti použití „přenosových" proměnných P1,P2,P3,P4 s doménami 0..1 D + E = 10*P1 + Y, Pl + N + R = 10*P2 + E, P2 + E + 0 = 10*P3 + N, P3 + S + M = 10*P4 + 0 P4 = M Hana Rudová, Omezující podmínky, 23. září 201 9 23 Úvod do CP Algebrogram: alternativy pro omezení nerovnosti Hana Rudová, Omezující podmínky, 23. září 201 9 24 Úvod do CP Algebrogram: alternativy pro omezení nerovnosti 28 omezení nerovnosti: X + Y pro X,Y e {S,E,N,D,M,0,R,Y} Hana Rudová, Omezující podmínky, 23. září 201 9 24 Úvod do CP Algebrogram: alternativy pro omezení nerovnosti 28 omezení nerovnosti: X + Y pro X,Y e {S,E,N,D,M,0,R,Y} 1 omezení pro nerovnost pro proměnné xi,...,xn s doménami Di,... ,Dn: al l_di fferent (x\,... ,xn) := {(di,..., dn) , di =/= d j pro i =/= j} Hana Rudová, Omezující podmínky, 23. září 201 9 24 Úvod do CP Optimalizační problém s podmínkami (COP) Problém splňování podmínek (X, D, C) Účelová funkce obj : Sol — W M Optimalizační problém s podmínkami (constraint optimization problem) M nalezení řešení d pro (X,D, C) takové, že obj(d) je optimálni ± optimální = maximální nebo minimálni Hana Rudová, Omezující podmínky, 23. září 201 9 25 Úvod do CP Problém batohu (knapsack problem) Je dán batoh velikosti man předmětů různé velikosti a ceny. Vyberte takové předměty, aby se vešly do batohu a jejich celková cena byla maximální. Batoh velikosti m Předměty velikosti Vi,..., vn a ceny ci,..., cn M Proměnné: Hana Rudová, Omezující podmínky, 23. září 201 9 26 Úvod do CP Problém batohu (knapsack problem) Je dán batoh velikosti man předmětů různé velikosti a ceny. Vyberte takové předměty, aby se vešly do batohu a jejich celková cena byla maximální. Batoh velikosti m Předměty velikosti Vi,..., vn a ceny ci,..., cn 3 Proměnné: Xi,... ,xn Domény: Hana Rudová, Omezující podmínky, 23. září 201 9 26 Úvod do CP Problém batohu (knapsack problem) Je dán batoh velikosti man předmětů různé velikosti a ceny. Vyberte takové předměty, aby se vešly do batohu a jejich celková cena byla maximální. Batoh velikosti m 3 Předměty velikosti Vi,..., vn a ceny ci,..., cn 3 Proměnné: Xi,... ,xn Domény: 0..1 Omezení: Hana Rudová, Omezující podmínky, 23. září 201 9 26 Úvod do CP Problém batohu (knapsack problém) Je dán batoh velikosti man předmětů různé velikosti a ceny. Vyberte takové předměty, aby se vešly do batohu a jejich celková cena byla maximální. Batoh velikosti m Předměty velikosti Vi,..., vn a ceny ci,..., cn 3 Proměnné: Xi,... ,xn Domény: 0..1 n 3 Omezení: ^ Ví.Xí < m M Účelová funkce: Hana Rudová, Omezující podmínky, 23. září 201 9 26 Úvod do CP Problém batohu (knapsack problem) Je dán batoh velikosti man předmětů různé velikosti a ceny. Vyberte takové předměty, aby se vešly do batohu a jejich celková cena byla maximální. Batoh velikosti m Předměty velikosti Vi,..., vn a ceny ci,..., cn 3 Proměnné: Xi,... ,xn Domény: 0..1 n 3 Omezení: ^ Ví.Xí < m n Účelová funkce: maximize ^ qxi i=l Hana Rudová, Omezující podmínky, 23. září 201 9 26 Úvod do CP Aplikace: přehled Operační výzkum 3 optimalizační problémy rozvrhování, plánování, alokace zdrojů Zpracování přirozeného jazyka 3 konstrukce parserů Počítačová grafika geometrické vztahy při analýze scény Databáze obnovení/zajištění konzistence dat 3 Molekulární biologie 3 DNA sekvencování 3 ... Hana Rudová, Omezující podmínky, 23. září 2019 27 Úvod do CP Příklad aplikace z MU: univerzitní rozvrhování Timetabling - Mozilla Firefox File Edit View History Bookmarks Tools Help <£D - - ^ í https://www.5rma5.puľ"due.edu/Tlmetabling/5electPnmaľYRote.do ahl ► ) H-|Google Timetable B Filter Export PDF Refresh Timetable Legend PHYS 112 [268] M o n PHYS 114 (273) M o n Tue 7:30a OLS 252 Lee 1 15 1 3 9:00a 9:30a ENGR 126R Lee 1 4 54 OLS 274 Lee 1 11:00a 11:30a 12:00p 12:30p 1:00p 1:30p 2:00p 2:30p 3:00p 3:30p 4:00p 4:30p 5:00p MA154Lec2 OLS 274 Lee3 PHYS 219 Lee 1 OLS 274 L 10 24 1 CGT163Lee1 ENGR 126A Lee 1 EP' 4. 3.0 OLS 252 Lee 1 15 1 3 PHYS 272 Lee 1 PHYS 221 Lee 1 PHYS 241 Lee 1 PHYS 241 Lee 2 PHYS 241 Lee 3 ENGR 126R Lee 1 OLS 274 Lee 1 4 54 PHYS 272 Lee 1 PHYS 221 Lee 1 PHYS 241 Lee 1 MA 154 Lee 2 OLS 274 Lee 3 PHYS 219 Lee 1 10 24 1 ENGR 126H Lee 1 4 69 PSY 335 SOC100 Lee 10 32 4 4 HIST 152 Lee 1 14 PHYS 241 Lee 3 ;GT163LabP 1 ■ 3R 126.A _i\ ENGR 126H Lee 1 4.69. 0 =■31 ?.?.:: .i: ' SOC100Lec10 32 4 4 HIST 152 Lee 1 14 CGT163Lec2 4 4 MA 154 Lee 2 10 9:30a 10:00a 10:30a 11:00a 11:30a 12:00p ANTH 205 Lee 1 16 61 PHYS 172H Lee 1 40 8 4 MA165 Lee 5 15 12:30p PHYS 2 1:00p 1:30p !:CCp 2:30p 3:00p 3:30p 4:00p 4:30p 5:00p 8 Lee 1 PHYS 218 Lee 2 MGMT201 Lec1 0.6.0 CGT163LabP2 4 5 4 PSY 200 Lee 1 24 38 MGMT201 Lec2 16 ANTH 205 Lee 1 16 61 ENGR 100H Lee 1a MA 165 Lee 5 4 6 15 Weekl ENGR 100H Lee 1b 4 6 Week 4 ENGR 100H Lee 1 www.smas.purdue.edu £g Proxy: None ^ O rozvrhovací systém Unitime http://www.unitime.org International Timetabling Competition 2019 co-organized by Fl MU: https://www.itc2019.org Hana Rudová, Omezující podmínky, 23. září 2019 28 Úvod do CP Univerzitní rozvrhování: proměnné a omezení Doménové proměnné čas výuky předmětu I: Timel, hodnoty: možné časy místnost výuky předmětu I: Rooml, hodnoty: identifikátory místností Hana Rudová, Omezující podmínky, 23. září 201 9 29 Úvod do CP Univerzitní rozvrhování: proměnné a omezení Doménové proměnné čas výuky předmětu I: Timel, hodnoty: možné časy 3 místnost výuky předmětu I: Rooml, hodnoty: identifikátory místností Omezující podmínky zakázaný čas: Timel =/= Prohibited minimální velikost místnosti: Rooml > ConstSize identifikátory místností uspořádány podle velikosti M ConstSize: nejmenší identifikátor místnosti s velikostí Size Hana Rudová, Omezující podmínky, 23. září 201 9 29 Úvod do CP Univerzitní rozvrhování: proměnné a omezení Doménové proměnné čas výuky předmětu I: Timel, hodnoty: možné časy 3 místnost výuky předmětu I: Rooml, hodnoty: identifikátory místností Omezující podmínky zakázaný čas: Timel =/= Prohibited minimální velikost místnosti: Rooml > ConstSize identifikátory místností uspořádány podle velikosti M ConstSize: nejmenší identifikátor místnosti s velikostí Size v jedné místnosti v každém čase nejvýše jeden předmět jeden vyučující učí nejvýše jeden předmět v každém čase Hana Rudová, Omezující podmínky, 23. září 2019 29 Úvod do CP Univerzitní rozvrhování: optimalizace Optimalizační kritéria výuka v preferovaných časech 3 cena za výuku předmětu I ve vybraném čase: CostTimel 3 CostTime = CostTimel + CostTime2 + ■ ■ ■ Hana Rudová, Omezující podmínky, 23. září 201 9 30 Úvod do CP Univerzitní rozvrhování: optimalizace Optimalizační kritéria výuka v preferovaných časech cena za výuku předmětu I ve vybraném čase: CostTimel 3 CostTime = CostTimel + CostTime2 + ■ ■ ■ výuka v preferovaných místnostech 3 cena za výuku předmětu I ve vybraném čase: CostRooml M CostRoom = CostRooml + CostRoom2 + ■ ■ ■ Hana Rudová, Omezující podmínky, 23. září 201 9 30 Úvod do CP Univerzitní rozvrhování: optimalizace Optimalizační kritéria výuka v preferovaných časech cena za výuku předmětu I ve vybraném čase: CostTimel 3 CostTime = CostTimel + CostTime2 + ■ ■ ■ M výuka v preferovaných místnostech cena za výuku předmětu I ve vybraném čase: CostRooml CostRoom = CostRooml + CostRoom2 + ■ ■ ■ dva předměty jednoho studenta by se neměly překrývat dva předměty IJ zároveň navštěvuje SIJ studentů Hana Rudová, Omezující podmínky, 23. září 201 9 30 Úvod do CP Univerzitní rozvrhování: optimalizace Optimalizační kritéria výuka v preferovaných časech cena za výuku předmětu I ve vybraném čase: CostTimel 3 CostTime = CostTimel + CostTime2 + ■ ■ ■ M výuka v preferovaných místnostech cena za výuku předmětu I ve vybraném čase: CostRooml CostRoom = CostRooml + CostRoom2 + ■ ■ ■ dva předměty jednoho studenta by se neměly překrývat dva předměty IJ zároveň navštěvuje SIJ studentů 3 CostOverlap = ^ SIJ IJ: timeOverlap(IJ) Hana Rudová, Omezující podmínky, 23. září 201 9 30 Úvod do CP Univerzitní rozvrhování: optimalizace Optimalizační kritéria výuka v preferovaných časech cena za výuku předmětu I ve vybraném čase: CostTimel 3 CostTime = CostTimel + CostTime2 + ■ ■ ■ M výuka v preferovaných místnostech cena za výuku předmětu I ve vybraném čase: CostRooml CostRoom = CostRooml + CostRoom2 + ■ ■ ■ dva předměty jednoho studenta by se neměly překrývat dva předměty IJ zároveň navštěvuje SIJ studentů 3 CostOverlap = ^ SIJ IJ: timeOverlap(IJ) minimize (WTime * CostTime + WRoom * CostRoom + WOverlap * CostOverlap) Hana Rudová, Omezující podmínky, 23. září 201 9 30 Úvod do CP