Globální podmínky
Globální podmínky
Globální podmínka: definována pro libovolný konečný počet proměnných Global Constraint Catalog
http://sofdem.gi thub.i o/gccat/
M Nicolas Beldiceanu, Mats Carlsson and Jean-Xavier Rampon
Popis omezení dostupných v literatuře a v systémech s omezujícími podmínkami
„The catalog presents a list of 423 global constraints issued from the literature in constraint programming and from popular constraint systems. The semantic of each constraint is given together with some typical usage and filtering algorithms, and with reformulations in terms of graph properties, automata, and/or logical formulae. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms."
PDF dokument, srpen 2014, cca 4 000 stran
Hana Rudová, Omezující podmínky, 21. října 2019 2
(Globální podmínky a) rozvrhován
Všechny proměnné různé
M all Different
3 Disjunktivní zdroj/rozvrhování
M dvar interval, dvar sequence «• noOverlap
3 Kumulativní zdroj/rozvrhování
M cumuFunction, pulse
Alternativní zdroje * alternative
Hana Rudová, Omezující podmínky, 21. října 2019
3
Všechny proměnné různé
Proměnné v poli Array jsou různé
M dvar int Array[Interval];
M globální podmínka: al 1 Different(Array) ;
M binární podmínky: for (i, j in Interval  : i  ! =
3 allDifferent vs. binární podmínky
M allDifferent má úplnou propagaci
binární podmínky mají slabší (neúplnou) propagaci
Příklad: učitelé musí učit v různé hodiny I
M  globální podmínka:
Jan = 6, Ota = 2, Anna = 5,
Marie = 1, Petr e{3,4}, Eva e {3,4} I
M  binární podmínky:
Jan e{3,...,6}, Petr e{3,4}, Annae {2,..., 5}, Ota g {2,3,4}, Eva e{3,4}, Marie e{l,...,6}
Hana Rudová, Omezující podmínky, 21. října 2019 4
j) Array[i]  != ArrayEj] ;l
I
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
Naivní propagace pro all Different
U = {Petr, Ota, Eva}, dom(U) = {2, 3, 4}:
{2,3,4} nelze pro Jan, Anna, Marie Jan g {5,6}, Anna = 5, Marie e {1,5,6}I
Konzistence: musí platit:
V{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u Dk} > k
M Inferenční pravidlol
M V: množina všech proměnných M U = {Xi,...,Xk}, dom(U) = {Di u ■ ■ ■ u Dk} M card(U) = card(dom(U)) => Vv e dom(U),\/X e (V - U),X + v 3 hodnoty v dom(U) jsou pro ostatní proměnné nedostupné
Složitost
hledání všech podmnožin množiny n proměnných (naivní) 0(2n)
Hana Rudová, Omezující podmínky, 21. října 201 9 5
učitel	min	max
Jan	3	6
Petr		4
Anna	2	5
Ota		4
Eva		4|_
Marie	1	6
Párování v bipartitních grafech
Efektivní propagaci pro allDifferent lze založit na párování v bipartitních grafech (Regin 94)
3 Bipartitní graf
uzly grafu rozdělené do dvou množin 3 neexistují hrany mezi uzly jedné množiny
Párování v bipartitních grafech
M v grafu neexistují dvě hrany, které by měly společný vrchol
Maximální párování
párování, které má maximální počet hraní
M CSP jako bipartitní graf
M jedna množina vrcholů reprezentuje proměnné
druhá množina vrcholů reprezentuje hodnoty proměnných 3 hrana z proměnné X do hodnoty a říká, že proměnná X může nabývat hodnoty al
Hana Rudová, Omezující podmínky, 21. října 2019 6
all Different - párování v bipartitních grafech II
Inicializace
sjednocení domén proměnné proměnných
S vypočti maximální párování
M odstraň všechny hrany, které nepatří do žádného maximálního párováníl
Propagace zmenšené domény
odstraň odpovídající hrany
3 vypočti nové maximální párování
M odstraň všechny hrany, které nepatří do žádného maximálního párováníl
Algoritmus založen na doménové konzistenci
3 každé maximální párování definuje doménovou podporu
M složitost 0(n2k2), n... počet proměnných, k... maximální velikost doményl
3 efektivnější algoritmus využívá konzistenci mezí - složitost O(nlogn) (Puget 1 998)
Hana Rudová, Omezující podmínky, 21. října 2019 7
Intervalové proměnné
Intervalová proměnná: pro modelování časového intervalu (úlohy, aktivity)
3 hodnotou intervalové proměnné je celočíselný interval [start, end) * příklad: dvar interval x in 0..1000000 size 100..200;
0 [100,200] 1000000
[.........ľ   i   '......]
I— —I Time
Volitelná intervalová proměnná: pro modelování časového intervalu, který může ale nemusí být přítomen v řešení (přítomný vs. nepřítomný interval)
např. pro modelování volitelných aktivit, které v řešení nemusí být
příklad: dvar interval x optional in 0..1000000 size in 100..200;
Dom(x) c {_l} u {[start, end)\start, end e Z,start < end} ± značí, že interval není přítomen v řešení
Hana Rudová, Omezující podmínky, 21. října 2019 8
Disjunktní/unární rozvrhování
Sekvenční proměnná p
definována na množině intervalových proměnných x
dvar interval x[i in l..n] dvar sequence p in x;
M hodnota intervalové proměnné p je permutace přítomných intervalů
pozor, permutace t ještě neimplikuje žádné uspořádání v časell I
Omezení noOverlap(p)
vyjadřuje, že sekvenční proměnná p reprezentuje řetězec nepřekrývajících se intervalových proměnných
pro vyjádření rozvrhování na unárním/disjunktivním zdroji, kde se intervaly/úlohy/aktivity nepřekrývají
3 poznámka: nepřítomné intervaly v řetězci zahrnuty nejsou
Hana Rudová, Omezující podmínky, 21. října 2019 9
Disjunktivní rozvrhování: princip algoritmu
Hledání hran (edge finding) - Baptisté & Le Pape, 1 996
Hledáme úlohu, která předchází nebo následuje množinu jiných úloh
dvar interval A in 4..16 size 2; dvar interval B in 6..16 size 4; dvar interval C in 7..15 size 5;
Co se stane, pokud nebude aktivita A zpracována jako první?
16
A(
I
B(4)
16
C(5)
15
Pro A,B,C není dost času, a tedy aktivita A musí být první
4h A(2) "I 7
6h
B(4)
16
Hana Rudová, Omezující podmínky, 21. října 2019
C(5)
10
15
Další podmínky: precedence
Mezi intervalovými proměnnými můžeme definovat precedenční podmínky:
dvar i nterval i; dvar i nterval j ;
endBeforeStart(i , j); endBeforeEnd(i, j); endAtStart(i, j) ; endAtEnd(i, j) ; startBeforeStart(i, j); startBeforeEnd(i, j); startAtStart(i, j); startAtEnd(i , j) ;
Poznámka: tyto podmínky platí, pokud jsou oba intervaly přítomné
Hana Rudová, Omezující podmínky, 21. října 2019
A dále: logické podmínky
Unární podmínka pro přítomnost intervalu x:
presenceOf(x)
znamená, že x =/= ± Příklady:
presenceOf(x) == presenceOf(y)   // x přítomen právě tehdy, když je přítomen y | presenceOf(x) => presenceOf(y)   // implikace presenceOf(x) => !presenceOf(y)
Pozor na použití:
precedenční podmínky: polynomiální složitost logické binární podmínky: polynomiální složitost precedence + logické binární: NP-těžké!
Hana Rudová, Omezující podmínky, 21. října 2019
12
Výrazy s intervalovými proměnnými
Pro vytváření účelových funkcí nebo definici omezení
startOf(x) endOf(x) sizeOf(x, V)
Příklad: minimalizace času dokončení poslední úlohy (tzv. makespanu)
minimize max(i in l..n) endOf(x[i])
Hana Rudová, Omezující podmínky, 21. října 2019
13
Příklad: rozvrhování problému job-shop
Job-shop problém:
problém rozvrhování úloh, které se skládají z nepřekrývajících operací každá operace úlohy prováděna na jiném stroji
pořadí operací úlohy předem určeno
op11	-►	op12	—>-	op13
op21
op22
op23
unarm stroje
op31
op32
op33
op41
op42
op43
1
2
3
4
5
6
7
8
9
10
11
[] M1 [] M2
□ M3| I
dvar interval op[j in Jobs] [p in Pos] size Ops [j] [p] .pt; dvar sequence mchs[m in Mens] in
all(j in Jobs, p in Pos: Ops [j] [p] .meh == m) op[j][p];
minimize max(j in Jobs) endOf(op[j] [nbPos]);
subject to { tuple Oper {
forali(m in Mchs) int mch; // Machine
noOverlap(mchs [m] ) ; ■ „_._// n
n      i -i / •   •     -r -i .    0 n int pt; // Processing time
forallCj in Jobs, p in 2..nbPos) j.
^    endBeforeStart(op[j] [p-1] ,op[j] [p] ) ; 0per 0'ps[j in Jobs] [m in Mchs] =
Hana Rudová, Omezující podmínky, 21. října 2019
14
př. 0ps[l] [2]=<3,6>
Kumulativní funkce
Hodnota výrazu kumulativní funkce reprezentuje vývoj kvantity v čase, která může být inkrementálně změněna (snížena nebo navýšena) intervalovými proměnnými.
Příklady:
intervaly využívají počty pracovníků M intervaly využívají skladové zásoby
Intervalové proměnné x [i] přispívají do kumul. funkce po dobu svého provádění
int wor[l..5] = [1,3,2,4,1];
cumul Function y = sum(i in 1..5)   pul se(x[i ] , wor [i ]) ;
A
pulse(xř 1)
0
Omezení na výrazech kumulativní funkce
X
Time
I
int h =
dvar int h =
cumulFunction f=
cumulFunction f=
f<=h
f<=h
Hana Rudová, Omezující podmínky, 21. října 2019
1 5
Příklad: RCPSP
Resource-contrained project scheduling problem (RCPSP)
1 dvar interval a[i in Tasks] size i.pt;
2 cumulFunction usage[r in Resources] =
3 sum(i in Tasks: i.qty[r]>0) pulse(a[i],i.qty[r]);
4 minimize max(i in Tasks) endOf(a[i]);
5 subject to {
6 forali(r in Resources)
7 usage[r] <= Capacity[r];
8 forali(i in Tasks, j in i.succs)
9 endBeforeStart(a[i], a[<j>]);
10 } <j> odkazuje jako klíč na celý tuple
Hana Rudová, Omezující podmínky, 21. října 2019
16
Alternativní podmínka
Pokud je interval x přítomný, pak je právě jeden z intervalů yl, . . . ,yn přítomný a je synchronizován s x (má stejný start a konec)
& alternative(x, [yl,...,yn])
Pokud je x nepřítomné, pak jsou yi také nepřítomnél Rozšíření: právě k intervalů z yl, . . . ,yn je synchronizováno s x
& alternative(x,  [yl,...,yn], k)   //k: celočiselný vyrazí
Příklad použití:
-0 každá intervalová proměnná x[t] vyžaduje nbWorkers[t] přítomných intervalů mezi
assigned[t] [w] pro pracovníky w |kód ještě nutno rošířit o nepřekrývání pro pracovníky).!
M dvar interval x[t in Tasks] size pt[u]; int nbWorkers[t in Tasks];
dvar interval assigned[Tasks][Workers] optional; forall (t in Tasks)
alternative(x[t], all (w in Workers) assigned[t][w], nbWorkers[t]);
Hana Rudová, Omezující podmínky, 21. října 201 9 1 7
Obecný konzistenční algoritmus
Konzistenční algoritmus pro nebinární podmiň
Obecný konzistenční algoritmus Varianta AC-3 s frontou proměnných rozšíření AC-2001 na nebinární podmínky! M Opakovaně se provádí revize podmínek, dokud se mění domény
procedure Nonbinary-AC-3-with-Variables(Q) while Q non empty do
vyber a smaž V j e Q for V C takové, že V j e scope(C) do W : = revise (V/, C)
// W je množina proměnných jejichž, doména se změnila if 3 Vi e W taková, že Di = 0 then return fail Q := Q u {W} end Nonbinary-AC-3-with-Variables
Hana Rudová, Omezující podmínky, 21. října 2019
19
Revizní procedura: různé typy konzistence
Speciální revise procedury jsou definovány v závislosti na typu omezení, tj. revise procedura může implementovat
obecnou hranovou konzistenci
konzistenci mezí
M konzistenční algoritmy pro globální podmínky jako allDifferent
Hana Rudová, Omezující podmínky, 21. října 2019
20
Revizní procedura
3 Uživatel má často možnost definovat vlastní revise proceduru
Je potřeba určit událost, která revizi vyvolá událostí je změna domény proměnné (suspension)
M vyvolání revize pouze při dané změně proměnné
& při libovolné změně domény (u obecné hranové konzistence) ±> při změně mezí (u konzistence mezí) ±> při instanciaci proměnné
M tj. pro každou proměnnou lze použít různé události
3 revize jednolivých podmínek jsou realizovány v závislosti na aktivaci odpovídající události (událostmi řízený výpočet)!
Je potřeba navrhnout propagaci přes podmínku pro danou událost
M výsledkem propagace je zmenšení domén proměnných M pro jednu podmínku lze mít více propagačních kódů
Hana Rudová, Omezující podmínky, 21. října 201 9 21
Základní konzistenční algoritmus s událostmi
-0 proceduře Nonbinary-AC-3-with-Events(Q) while Q non empty do
vyber a smaž event(Vj) G Q
for V C takové, že V) e scope(C) a C čeká na event(Vj) do W : = revi se (event (V)), C) // jsou vyvolány pouze ty revize, které čekaji na danou event(Vj) // W je množina proměnných jejichž, doména se změnila if 3 Vi G W taková, že Dt = 0 then return fail Q := Q u {W} end Nonbinary-AC-3-with-Events
Hana Rudová, Omezující podmínky, 21. října 2019
22