Restrições Globais
• Em muitos casos, interessa definir restrições n-árias
primitivas,
– quer por facilidade de modelação,
– quer para explorar algoritmos especializados que
permitam uma propagação eficiente.
• Exemplo: Garantir que n variáveis tomam valores
diferentes.
all_dif ([A1, A2, ..., An]
• Alternativas
– Definir a restrição a partir de restrições binárias .
– Definir (utilizar) uma restrição global primitiva
1
Restrições Globais
A definição da restrição a partir de restrições binárias
de diferença () não coloca dificuldades de modelação,
podendo ser feita com um predicado recursivo.
all_diff([]).
all_diff([H|T]):one_diff(H,T),
all_diff(T).
one_diff(_,[]).
one_diff(X,[H|T]):X #\= H,
one_diff(X,T).
2
Restrições Globais
• No entanto, a propagação das restrições binárias, não
permite grandes reduções de domínio.
• Exemplo:
X1:
X2:
X3:
X4:
X5:
1,2,3
1,2,3,4,5,6
1,2,3,4,5,6,7,8,9
1,2,3,4,5,6
1,2,3
X6:
X7:
X8:
X9:
1,2,3,4,5,6,7,8,9
1,2,3,4,5,6,7,8,9
1,2,3
1,2,3,4,5,6
• É facil de ver que a propagação das restrições binárias,
quer para manter a consistência de nó, quer para manter a
consistência de arco, não produzem nenhuma redução dos
domínios das variáveis.
• E, no entanto, é fácil inferir essa redução !
3
Restrições Globais
• As variáveis X1, X5 e X8 só podem tomar os valores 1, 2 e
3. Como a estas três variáveis correspondem três
valores, estes têm de ser retirados das outras variáveis
X1: 1,2,3
X2: 1,2,3,4,5,6
X3: 1,2,3,4,5,6,7,8,9
X4: 1,2,3,4,5,6
X5: 1,2,3
X6: 1,2,3,4,5,6,7,8,9
X7: 1,2,3,4,5,6,7,8,9
X8: 1,2,3
X9: 1,2,3,4,5,6
• Agora são as variáveis X2, X4 e X9 que só podem tomar
os valores 4, 5 e 6, que devem ser retirados das outras
variáveis.
X1: 1,2,3
X2: 1,2,3,4,5,6
X3: 1,2,3,4,5,6,7,8,9
X4: 1,2,3,4,5,6
X5: 1,2,3
X6: 1,2,3,4,5,6,7,8,9
X7: 1,2,3,4,5,6,7,8,9
X8: 1,2,3
X9: 1,2,3,4,5,6
4
Restrições Globais
• Neste caso, os cortes no domínio das variáveis poderiam
ser obtidos por manutenção de consistência 4.
• Por exemplo, analisando as variáveis X1, X2, X5 e X8, seria
fácil verificar que das d4 potenciais atribuições de
variáveis, nenhuma atribuição admissível inclui X2 = 1
(nem X2 = 2, nem X2 = 3).
• No entanto essa manutenção é em geral muito “cara”
computacionalmente. Para cada combinação de 4 variáveis
haveria de testar d4 tuplos, com complexidade O(n4 d4)
• Apesar de polinomial no número de variáveis e no seu
domínio, este tipo de consistência “forte” e não produz
em geral cortes que contrabalancem o seu custo.
5
Restrição Global - all_diff
• No entanto, e para este predicado particular, existe um
algoritmo que permite fazer esses cortes, com uma
técnica muito diferente da simples propagação.
• Esse algoritmo, descrito em [Regi94] é baseada na
teoria de grafos, e utiliza a noção de emparelhamento
(“matching”).
• Assim a uma restrição all_diff é associado um grafo
bipartido, variáveis e valores, cujos arcos ligam as
variáveis aos respectivos domínios.
• Em tempo polinomial é possível eliminar desse grafo os
arcos que não correspondem a atribuições possíveis das
variáveis.
6
Restrição Global - all_diff
Ideias Base:
• A cada valor possível de uma variável corresponde um
arco no grafo bipartido.
• Um emparelhamento (“matching”) corresponde a um
subconjunto de arcos, ligando variáveis a valores
diferentes.
• Um emparelhamento máximo é um emparelhamento
incluindo todas as variáveis.
• Uma solução da restrição all_diff corresponde a um
emparelhamento máximo.
7
Restrição Global - all_diff
Exemplo:
A,B:: 1..2, C:: 1..3, D:: 2..5, E:: 3..6,
all_diff([A,B,C,D,E]).
A
1
B
2
C
3
D
4
E
5
Emparelhamento
Máximo
A = 1
B = 2
C = 3
D = 4
E = 5
6
8
Restrição Global - all_diff
A filtragem é baseada nos seguintes princípios:
1.
Se um arco não pertence a nenhum emparelhamento
máximo, então ele não pertence a uma solução.
2. Uma vez determinado um emparelhamento máximo
arbitrário é possível determinar se qualquer arco
pertence ou não a um emparelhamento máximo.
3. Com efeito, dado um emparelhamento máximo
arbitrário, um arco pertence a um emparelhamento
máximo sse pertencer:
a) A um ciclo alternado par; ou
b) A um caminho alternado par, começando num
vértice livre;
9
Restrição Global - all_diff
Exemplo: Para o emparelhamento máximo (EM) indicado
• 6 é um vértice livre;
• 6-E-5-D-4 é um caminho alternado A
par, alternando arcos do EM (E-5, D-4)
B
com arcos fora do EM (6-E e 5-D);
1
• A-1-B-2-A é um ciclo alternado;
C
3
• E-3 não pertence a um ciclo alternado
D
4
• E-3 não pertence a um caminho
E
alternado par começado no vértice
livre (6)
5
2
6
• E-3 pode ser filtrado!
10
Restrição Global - all_diff
Compactação
• Antes desta análise, o grafo pode ser compactado,
aglutinandojuntando nós “equivalentes”, i.e que
pertencem a ciclos alternados.
• A justificação é que para qualquer solução envolvendo
as variáveis e valores dum ciclo alternado se podem
obter outras por permutação das correspondências.
• Desta forma basta fazer a análise de filtragem com
base numa dessas soluções, agrupando num só os
vértices de valores e noutros os das variáveis.
11
Restrição Global - all_diff
A
B
C
D
E
1 • A-1-B-2-A é um ciclo alternado;
2 • Por permutação das variáveis A e B a
solução <A,B,C,D,E> = <1,2,3,4,5> tornase <A,B,C,D,E> = <2,1,3,4,5>
3
• Então podem agrupar-se os nós A e B e
4
os nós 1 e 2. Pela mesma razão, podem
ser agrupados os nós D/E e os nós 4/5.
5
A/B
1/2
6
C
3
Com estas simplificações, é
D/E
4/5
obtido o grafo compactado
6
12
Restrição Global - all_diff
A análise do grafo compactado permite concluir que
A/B
C
D/E
1/2
3
4/5
6
• O arco D/E - 3 pode ser filtrado
(notar que, apesar de pertencer
ao ciclo D/E - 3 - C - 1/2 - D/E,
este ciclo não é alternado)
• Os arcos D/E - 1/2 e C - 1/2
também podem ser filtrados.
A/B
O grafo compactado pode
asssim ser simplificado para
C
D/E
1/2
3
4/5
6
13
Restrição Global - all_diff
Expandindo, após a simplificação, o grafo compactado
A/B
C
D/E
1/2
3
4/5
6
A
1
B
2
C
3
D
4
E
5
6
O que fixa imediatamente C=3 e, mais geralmente filtra
os domínio iniciais, para
A,B:: 1..2, C:: 1,2,3, D:: 2,3,4,5, E:: 3,4,5,6
14
Propagação da Restrição all_diff
Após a eliminação de arcos por outras restrições, a
restrição all_dif permite a propagação de restrições
(eliminação de arcos) de uma forma incremental.
Existem 3 situações a considerar:
1. Eliminação de um arco vital (único arco ligando uma
variável a um valor) - A restrição torna-se impossível
A
1
A
1
B
2
B
2
C
3
C
D
4
D
4
E
5
E
5
6
?
3
6
15
Propagação da Restrição all_diff
2. Eliminação de um arco não-vital que não-pertence a
um emparelhamento máximo
- Eliminar os arcos que deixam de fazer parte dos
ciclos e caminhos alternados
A
1
A
1
B
2
B
2
C
3
C
3
D
4
D
4
E
5
E
5
6
6
O arco A-4 deixa de pertencer a um caminho alternado
começado no nó 6. D-5 deixa de pertencer a esse caminho
16
alternado, mas ainda pertence a um ciclo alternado.
Propagação da Restrição all_diff
3. Eliminação de um arco não-vital que pertence a um
emparelhamento máximo
- Determinar um novo emparelhamento máximo e
recomeçar de novo
A
1
A
1
B
2
B
2
C
3
C
3
D
4
D
4
E
5
E
5
6
6
O novo emparelhamento máximo inclui os arcos D-5 e E-6.
Com este emparelhamento, os arcos E-4 e E-5 deixam de
pertencer a caminhos ou ciclos alternados.
17
Restrição Global - all_diff
Complexidade:
Assumindo n variáveis em que cada uma tem um domínio
com d valores, sendo D a cardinalidade da união de todos
os domínios,
1. É possível obter um emparelhamento máximo com uma
complexidade temporal O(dnn).
2. É possível remover arcos que não pertencem a nenhum
emparelhamento máximo com uma complexidade
temporal de O( dn+n+D).
3. Somando estes resultados obtemos O(dn+n+D+dnn).
Tendo em conta que D < dn, a complexidade total do
algoritmo é de apenas O(dnn).
18
Restrição Global - all_diff
Disponibilidade:
1.
A restrição all_diff apareceu inicialmente no sistema
CHIP (algoritmo?).
2.
A implementação descrita está incorporada no sistema
ILOG, disponibilizada pela primitiva IlcAllDiff
3.
Este algoritmo, está igualmente disponibilizados no
sistema SICStus, através da primitiva all_distinct/1.
Versões do algoritmo menos completas (com menores
cortes) são igualmente disponibilizadas pela primitiva
all_different/2 em que o segundo argumento é um
parâmetro que controla as opções disponíveis.
19
Restrição Global - all_diff
Exemplo ( programa all_different.txt):
adn([A,B,C,D,E,F,G,H,I,J]):A in 0..9, B in 0..8, C in 0..7, D in 0..6, E in 0..5,
F in 0..4, G in 0..3, H in 0..2, I in 0..1, J in 0..1,
statistics(runtime,[_,_]),
all_different([A,B,C,D,E,F,G,H,I,J]),
labeling([],[A,B,C,D,E,F,G,H,I,J]),
statistics(runtime,[_,T]),
nl,write('T'-T), nl,
fd_statistics.
20
Restrição Global - all_diff
Exemplo:
?- ad3(L).
?- ad1(L).
T-0
Resumptions: 2
Entailments: 1
Prunings: 20
Backtracks: 0
Constraints created: 1
L=[9,8,7,6,5,4,3,2,0,1]?
yes
T-150
Resumptions: 38763
Entailments: 33203
Prunings: 31700
Backtracks: 5560
Constraints created: 4
L=[9,8,7,6,5,4,3,2,0,1]?
yes
21
Restrição Global - Assignment
A restrição all_diff é aplicável a problemas em que se
pretende que tarefas diferentes sejam executadas por
agentes diferentes (ou utilizem recursos diferentes).
No entanto, as tarefas e os recursos são tratados
diferentemente. Uns são variáveis e outros são
simplesmente domínios dessas variáveis. Por exemplo,
denotando 4 tarefas/recursos pelas variáveis Ti/Rj,
haveria que optar por uma das especificações
T1 in 1..3, T2 in 2..4, T3 in 1..4, T4 in 1..3.
R1 in {1,3,4}, R2 in 1..4, R3 in 1..4, R4 in {2,3}
Assim, podem-se especificar outras restrições com as
variáveis Ti ou Rj, mas não se podem especificar
(facilmente) restrições que envolvam ambas.
22
Restrição Global - Assignment
Esta “desigualdade” pode ser ultrapassada tratando quer
as tarefas quer os recursos de uma forma similar, através
da sua representação através de variáveis.
No entanto, há que ter o cuidado de garantir que se pelo
lado das tarefas uma tarefa j é executada pelo recurso i,
pelo lado dos recursos, o recurso i é atribuído à tarefa j.
Assim, continuando a denotar tarefas por Ti e recursos
por Rj temos para quaisquer i, j 1..n
R i = j  Tj = i
Este é o objectivo da restrição assignment/2,
disponibilizada no SICStus, que utiliza as mesmas técnicas
de propagação da restrição all_diff.
23
Restrição Global - Assignment
Exemplo:
A1:1..2, A2::1..2, A3::1..3, A4::2..5, A5:: 3..5,
B1:1..3, B2::1..4, B3::3..5, B4::4..5, B5:: 4..5,
assignment([A1,A2,A3,A4,A5], [B1,B2,B3,B4,B5]).
A1
B1
A2
B2
A3
B3
A4
B4
A5
B5
A = 1
B = 2
emparelhamento
máximo
C = 3
D = 4
E = 5
24
Restrição Global - Assignment
Como a restrição de assignment impõe um emparelhamento
máximo no grafo bipartido de “tarefas” e “recursos”, pelo
que se poderão usar a mesma técnica de filtragem da
restrição all_diff.
A1
B1
A1
B1
A2
B2
A2
B2
A3
B3
A3
B3
A4
B4
A4
B4
A5
B5
A5
B5
25
Restrição Global - Assignment
Desta forma os domínios iniciais
A1:1..2, A2::1..2, A3::1..3, A4::2..5, A5:: 3..5,
B1:1..3, B2::1..4, B3::3..5, B4::4..5, B5:: 4..5,
A1
B1
A1
B1
A2
B2
A2
B2
A3
B3
A3
B3
A4
B4
A4
B4
A5
B5
A5
B5
São filtrados para
A1:1..2, A2::1..2, A3::
B1:1..2, B2::1..2, B3::
3 , A4::4..5, A5:: 4..5,
3 , B4::4..5, B5:: 4..5,
26
Restrição Global - Circuit
• As restrições globais anteriores podem ser vistas
como impondo uma “permutação” das variáveis.
• Em vários problemas essa permutação não é uma
restrição suficiente, sendo necessário considerar
uma “ordenação” das variáveis.
• Uma situação típica é a necessidade de impôr uma
sequenciação de tarefas, havendo precedências entre
tarefas e não podendo certas tarefas ser
“adjacentes”.
• Nestas situações, para além da permutação das
variáveis, pretende-se obter um ciclo viável das
tarefas, e a não existência de sub-ciclos.
27
Restrição Global - Circuit
Estes problemas podem ser descritos através de
grafos, cujos nós representam tarefas e os arcos
denotam precedências entre essas tarefas.
2
A
A
B
4
C
2
C
D
2
2
B
3
5
7
6
8
D
9
Os arcos podem ser etiquetados por “propriedades”
das precedências. Por exemplo, tempos de transição.
Este tipo de restrições globais aplica-se a vários
problemas do tipo “caixeiro viajante”.
28
Restrição Global - Circuit
Filtragem: Para este tipo de problemas, pretende-se
eliminar os arcos que não pertençam a nenhum circuito
hamiltoniano (caixeiro viajante).
No grafo é fácil de ver que os únicos circuitos possíveis
são A->B->D->C->A e A->C->D->B->A. Assim certos
arcos (ex. B->C, B->B) não podem pertencer a nenhum
circuito e podem ser eliminados.
A
B
A
B
C
D
C
D
29
Restrição Global - Circuit
A eliminação dos arcos que não pertencem a nenhum
circuito redundante é o objectivo da restrição global
circuit/1, disponibilizada no SICStus.
Esta restrição aplica-se a uma lista de variáveis de
domínio, em que o domínio de cada variável corresponde
ao conjunto de arcos ligando essa variável às outras,
denotadas pela ordem em que aparecem na lista.
A/1
A=2
B/2
A=3
C/3
D/4
Por exemplo:
A in 2..3,
B in 1..4,
C in 1..4,
D in 2..3,
circuit([A,B,C,D]).
30
Restrição Global - Circuit
A restrição global circuit/1 permite obter a eliminação
dos arcos que não pertencem a nenhuma solução. Por
exemplo, dado o golo
A in 2..3, B in 1,2,3,4, C in 1,2,3,4, D in 2..3,
circuit([A,B,C,D]).
A
B
A
B
C
D
C
D
Obtém-se o resultado
A in 2..3, B in 1,2,3,4, C in 1,2,3,4, D in 2..3.
31
Restrição Global - Element
Em várias situações, uma variável não só tem os seus
valores restringidos pelos valores de outra variável, como
é definida condicionalmente em função destes valores.
Por exemplo, o valor X do arco
que sai do nó A, depende do
valor deste nó;
se A = 2 então X = 3,
se A = 3 então X = 4;
caso contrário X = indefinido
2
A/1
4
2
2
B/2
3
2
5
C/3
7
6
8
D/4
9
Desta forma, a disjunção implícita nesta definição
condicional levanta, como é sabido, problemas de
eficiência na propagação de restrições.
32
Restrição Global - Element
Com efeito, o valor de X só poderá ser conhecido na
altura da enumeração (labelling) da variável A. Até
essa altura, pouco se pode inferir do valor de X.
2
se A = 2 então X = 3,
se A = 3 então X = 4;
caso contrário X = indefinido
A/1
4
2
2
B/2
3
2
5
C/3
7
6
8
D/4
9
Por outro lado, caso outras restrições do problema
impusessem que X < 4, uma propagação eficiente desta
condição deveria não só impôr X = 3 como também A = 2.
33
Restrição Global - Element
O tratamento eficiente deste tipo de disjunções é o
objectivo
da
restrição
global
element/3,
disponibilizada nas linguagens SICStus e CHIP.
element(X, [V1,V2,...,Vn], V)
Nesta restrição X é uma variável de domínio 1..n, e os
Vis são variáveis de domínio finito ou constantes. A
semântica da restrição pode ser descrita através da
equivalência
X = i  V = Vi
Do ponto de vista da propagação esta restrição
mantém coerência de domínio em X e coerência de
intervalo em V. Está particularmente optimizada para
o caso em que todos os Vis são constantes.
34
Restrição Global - Element
Exemplo (caixeiro.txt): Determinar um (ou mais) circuito
hamiltoniano no grafo abaixo, cujo comprimento não
exceda um valor máximo (20).
2
circ([A,B,C,D], Max, Circ):A in 2..3, B in 1..4,
C in {1}\/{3,4}, D in 2..3,
circuit([A,B,C,D]),
element(A,[_,2,3,_],Ca),
element(B,[2,2,5,6],Cb),
element(C,[2,_,2,9],Cc),
element(D,[_,8,7,_],Cd),
Circ #= Ca+Cb+Cc+Cd,
Circ #=< Max,
labeling([],[A,B,C,D]).
A/1
4
2
2
B/2
3
2
5
C/3
7
6
8
D/4
9
35
Restrição Global - Cycle
Por vezes pretende-se que os vários nós possam ser
ligados por mais de um circuito.
Esta situação corresponde ao clássico problema do
Caixeiro Viajante Múltiplo, que modela bem várias
situações práticas.
Por exemplo, se se pretenderem abastecer um conjunto
de estações de serviço com N auto-tanques.
Para este efeito, a linguagem CHIP extendeu a restrição
global circuit/1, para uma outra cycle/2, em que o primeiro
argumento é uma variável de domínio ou um inteiro
correspondente ao número de ciclos.
Nota: Na realidade a restrição circuit(L) é implementada
em CHIP como cycle(1,L).
36
Restrição Global - Cycle
Exemplo:
X1::[1,3,4]
X2::[1,3]
X3::[2,5,6]
X4::[2,5]
X5::[6]
X6::[4,5]
1
3
5
2
4
6
?- N::[1,2,3], X = [X1,X2,X3,X4,X5,X6], cycle(N,X).
N = 1
X =[3,1,5,2,6,4]
N = 2
N = 3
X =[3,2,1,5,6,4] X =[3,1,5,2,6,4]
1
3
5
1
3
5
1
3
5
2
4
6
2
4
6
2
4
6
37
Cardinalidade - Local e Global
Em muitos problemas, nomeadamente de escalas e horários
pretende-se exprimir restrições do tipo
Nestes N “slots” M devem ser do tipo T.
Em geral, já vimos como este tipo de restrições pode ser
“eficientemente” tratado com a meta-restrição de
cardinalidade. Em alguns sistemas/linguagens, estas
restrições de cardinalidade são dadas ou como primitivas
ou implementadas a partir da reificação de restrições.
Em particular, no SICStus pode ser usada a primitiva
count/4 para “contar” elementos numa lista, o que
substitui a meta-restrição de cardinalidade (ver adiante).
No entanto, a cardinalidade pode ser mais eficientemente
propagada se considerada de uma forma global.
38
Cardinalidade - Local e Global
Por exemplo, assumamos numa escala de serviço para uma
equipa de várias pessoas (enfermeiras), das quais uma ou
duas têm de fazer o turno da manhã (m), uma ou duas o
turno da tarde (t), uma o turno da noite (n), podendo as
outras ficar de folga (f) ou em reserva (r).
Para modelar este problema, vamos considerar uma lista L,
cujas variáveis Li correspondem às 7 pessoas disponíveis e
podem tomar valores no conjunto {m, t, n, f, r}.
Quer em SICStus quer em CHIP esta restrição complexa
pode ser partida em várias restrições de cardinalidade.
Para evitar as limitações dessas linguagens façamos a
codificação m/1, t/2, n/3, f/4, e r/5.
39
Cardinalidade - Local e Global
SICStus:
count(1,L,#>=,1), count(1,L,#=<,2)
count(2,L,#>=,1), count(2,L,#=<,2)
count(3,L,#=, 1) ,
count(4,L,#>=,0), count(4,L,#=<,2)
count(5,L,#>=,0), count(5,L,#=<,2)
%
%
%
%
%
um ou dois
um ou dois
um e um só
zero a dois
zero a dois
m/1
t/2
n/3
f/4
r/5
CHIP (ver [BeCo94] para detalhes - sintaxe modificada):
among([1,2],L,_,[1]),
among([1,2],L,_,[2]),
among( 1 ,L,_,[3]),
among([0,2],L,_,[4]),
among([0,2],L,_,[5]),
%
%
%
%
%
um a dois
um a dois
um e um só
zero a dois
zero a dois
m/1
t/2
n/3
f/4
r/5
40
Cardinalidade - Local e Global
No entanto, o tratamento local de cada uma destas
restrições, separadamente, não detecta todas as
oportunidades de filtragem de valores às variáveis. Por
exemplo:
A,B,C,D::{m,t}, E::{m,t,n}, F::{t,n,f,r}, G ::{n,r}
A
B
m (1,2)
C
t (1,2)
D
n (1,1)
E
f (0,2)
F
r (0,2)
G
41
Cardinalidade - Local e Global
A, B, C e D só podem tomar valores m e t. Como estes só
podem ser atribuidos a 4 pessoas, mais ninguém
(nomeadamente E) pode tomar valores m e t.
Como E só pode tomar o valor n, que deve ser tomado por
uma só pessoa, mais ninguém (F e G) pode tomar o valor e.
A
A
B
m (1,2)
B
m (1,2)
C
t (1,2)
C
t (1,2)
D
n (1,1)
D
n (1,1)
E
f (0,2)
E
f (0,2)
F
r (0,2)
F
r (0,2)
G
G
42
Cardinalidade - Local e Global
Este tipo de filtagem obtém-se através de um algoritmo
que utiliza analogias com fluxos em redes [Regi96].
Em primeiro lugar considera-se uma restrição global, gcc/4
que dada a lista de k variáveis X = [X1, ..., Xk] , que podem
tomar valores na lista com m valores v = [v1, ..., vm], sendo
cada um dos valores Vi atribuído a entre Li e Mi variáveis.
Assim, m restrições SICStus (ou equivalentes):
...
count(vi,X,#>=,Li), count(vi,X,#=<,Mi)
...
podem ser subtituídas pela restrição
gcc([X1,...,Xk], [v1,...,vm], [L1,..., Lm],[M1,..., Mm])
43
Cardinalidade - Local e Global
À restrição gcc
faz-se corresponder um grafo
direccionado (uma rede) com capacidades máximas e
limites mínimos nos arcos, e com dois nós adicionais, a e b.
Por exemplo:
gcc([A,,...,G],[m,t,n,f,r],[1,1,1,0,0], [2,2,1,2,2])
A
0;1
b
0;1
B
m (1,2)
C
t (1,2)
D
n (1,1)
E
f (0,2)
F
r (0,2)
G
1;2
1;2
1;1
a
0;2
0;2
0;
44
Cardinalidade - Local e Global
Uma solução do problema corresponde a um fluxo entre os
dois nós acrescentados, com fluxo unitário nos arcos que
ligam os valores às variáveis. Nestas condições, é valido o
Teorema: Uma restrição com k variáveis é consistente sse
existir um fluxo máximo de valor k entre os nós a e b.
A
0;1
0;1
B
m (1,2)
C
t (1,2)
D
n (1,1)
E
f (0,2)
0
F
r (0,2)
1
G
b
Fluxos
i
i
7
2
1;2
2 1;2
1;1
a
0;2
0;2
0;
45
Cardinalidade - Local e Global
Naturalmente no contexto desta restrição pretende-se
1. Obter um fluxo máximo com valor k, isto é mostrar que
o problema tem solução
2. Eliminar os arcos entre valores e variáveis que não
sejam percorridos em nenhuma solução de fluxo
máximo, isto é não pertencem a nenhuma solução.
3. Caso alguns arcos sejam eliminados (por outras
restrições, refazer 1 e 2 de forma incremental)
Em [Regi96] é apresentada uma solução para estes
problemas, bem como a sua complexidade polinomial.
46
Cardinalidade - Local e Global
1. Obter um fluxo máximo com valor k
Este problema de optimização pode ser resolvido muito
eficientemente por programação linear, sendo garantidas
as condições de integralidade dos valores dos fluxos nos
vários arcos.
No entanto, e tendo em conta o aspecto incremental
referido atrás, pode obter-se um fluxo máximo indo
utilizando caminhos de aumento no grafo residual, até não
ser possível aumentar mais um dado fluxo.
O grafo residual é igualmente um grafo direccionado, com
os mesmos vértices do grafo inicial. Os seus arcos, com
limite mínimo 0, tem uma capacidade residual que tem em
conta a capacidade não usada pelo fluxo f.
47
Cardinalidade - Local e Global
1. Grafo Residual de um fluxo f
a. Dado um arco (a,b) com capacidade c(a,b) e fluxo f(a,b)
tal que f(a,b) < c(a,b) existe um arco (a,b) no grafo residual
com capacidade residual cr(a,b) = c(a,b) - f(a,b).
O facto de o sentido ser idêntico indica que se pode
aumentar o fluxo no arco de um valor cr(a,b).
b. Dado um arco (a,b) com limite mínimo l(a,b) e fluxo f(a,b)
tal que f(a,b) > c(a,b) existe um arco (b,a) no grafo residual
com capacidade residual cr(a,b) = f(a,b) - l(a,b).
O facto de o sentido ser oposto indica que se pode reduzir
o fluxo no arco de um valor cr.
48
Cardinalidade - Local e Global
Exemplo: Dado o fluxo abaixo, com valor 6 (inferior ao
máximo), obtem-se o seguinte grafo residual.
2
2
2
2 2
2
1
0
2
2
6
6
49
Cardinalidade - Local e Global
Havendo um arco (a,b) (no grafo residual) com fluxo não
seja igual ao valor de cr, ele pode ser aumentado desde
que se obtenha um caminho de aumento do fluxo, entre os
nós a e b, no grafo residual.
No exemplo abaixo, este caminho permite obter um fluxo
máximo no grafo original.
2
2
2 2
2
2
1
0
2
2
1
7
50
Cardinalidade - Local e Global
A garantia de que um algoritmo incremental obtem um
fluxo máximo é dada pelo seguinte
Teorema: Um fluxo f entre os nós a e b é máximo sse não
existe nenhum caminho de aumento de f entre esses nós.
De uma forma semelhante se pode definir um caminho de
redução de fluxo entre os nós a e b, como um caminho no
grafo residual entre os nós b e a, como no exemplo
2
2
0
2
1
2
1 2
1
2
2
5
51
Cardinalidade - Local e Global
Complexidade
A procura de um caminho de aumento pode ser obtida
através de uma pesquisa em largura com complexidade
O(k+d+), em que  é o número de arcos entre as variáveis e
os valores e d o número de valores totais. Como   kd este
é o termo assimptoticamente dominante, pelo que a
complexidade é limitada por O().
Para se obter um fluxo máximo teremos de obter um
máximo de k caminhos de aumento, um para cada arco de
saída das k variáveis. A complexidade do método é pois de
ordem k O().
Como   kd, temos uma complexidade de ordem O(k2d)
para obtenção de um fluxo máximo a partir de um fluxo
nulo ( e menor a partir de um fluxo não máximo).
52
Cardinalidade - Local e Global
Para eliminar os arcos que não correspondem a valores
possíveis para as variáveis podemos fazer uso do
Teorema: Seja dado um fluxo máximo arbitrário f entre os
dois nós, a e b. Entre quaisquer dois nós x e y, o fluxo
f(x,y) é igual a qualquer outro f´(x,y) induzido entre esses
nós por outro fluxo máximo f’ sse os arcos (x,y) e (y,x) não
estiverem incluídos num ciclo com mais de 3 nós no grafo
residual (que passem nos nós a e b).
A justificação deste teorema é de que não havendo um
ciclo entre os dois nós, não pode haver um caminho de
aumento (entre x e y) nem de redução (entre y e x) pelo
que o fluxo se deverá manter constante entre os nós x e y,
para todos os fluxos máximos (a garantia de serem fluxos
máximos é dada pelo facto dos ciclos não passarem por a e
b não aumentando nem diminuindo o fluxo entre esses nós).
53
Cardinalidade - Local e Global
O teorema anterior permite eliminar do grafo todos os
arcos com fluxo nulo que não estejam em ciclos.
Dada a equivalência entre fluxo máximo e consistência da
restrição gcc, se nenhum fluxo máximo passa por um arco
entre um nó valor v e um nó variável x, então em nenhuma
atribuição de valores às variáveis consistente com a
restrição gcc a variável x pode tomar o valor v.
A filtragem de arcos permitida por este método é
exemplificada com o problema inicial.
54
Cardinalidade - Local e Global
Exemplo: Dado o fluxo máximo, com valor 7, obtem-se o
seguinte grafo residual.
2
2
2
2 2
2
1
0
2
2
6
7
55
Cardinalidade - Local e Global
Neste grafo residual os únicos caminhos com 3 vértices,
que não passam por a e b são os indicados. Incluindo (a
azul) os arcos com fluxo não nulo, obtemos todos os arcos
entre nós valor e nós variáveis que podem pertencer a uma
atribuição de valores às variáveis consistente com a
restrição gcc/4.
2
2
2
7
2
56
Cardinalidade - Local e Global
Com efeito, podemos comparar o grafo obtido após a
eliminação dos arcos e aquele que inicialmente tinhamos
considerado.
A
2
B
m (1,2)
C
t (1,2)
D
n (1,1)
E
f (0,2)
F
r (0,2)
G
57
Cardinalidade - Local e Global
Complexidade
A obtenção dos ciclos com mais de 3 nós, corresponde a
obter os subgrafos ligados fortemente, o que pode ser
feito com um algoritmo de complexidade O(m+n) para um
grafo com m nós e n arcos. No caso, m = k+d+1 e n  kd+d,
donde uma complexidade global O(kd+2d+k+1)  O(kd)
Em termos incrementais, por cada valor retirado ao domínio
de uma variável, poderá ser necessário recalcular um fluxo
máximo complexidade O(k2d) e eliminar os valores
inconsistentes complexidade O(kd), com complexidade
total
O(k2d+kd)  O(k2d).
58
Restrição Global - Flow
Recentemente [BoPA01] foi proposta uma restrição global
para modelar e resolver problemas de fluxos de redes que
aparecem em várias aplicações, nomeadamente problemas
de transportes, comunicações e cadeias de produção.
O objectivo desta restrição global é, tal como as
anteriores a de ser integrada num contexto de outras
restrições e permitir uma filtragem eficiente de valores
que não seria possível obter através da formulação dessa
restrição por um conjunto de restrições mais simples.
A sua utilização é descrita para problemas de fluxos
máximos, planeamento de produção e escalonamento de
pessoal.
59
Restrição Global - Sequênciação
Em alguns casos pretende-se não só garantir que num
conjunto de variáveis cada valor não apareça mais/menos
do que um certo número de vezes.
Pretende-se adicionalmente considerar esse conjunto de
variáveis como uma sequência, e garantir que para certas
sub-sequências o número de vezes que certos valores
aparecem seja limitado.
Esta situação é bem exemplificada no problema da
sequenciação de carros, em que não apenas se pretende
garantir uma restrições de cardinalidade mas igualmente
restrições de sequenciação.
60
Restrição Global - Sequência
Pretendem-se construir 10 carros em sequência numa linha
de montagem com diferentes opções (1 a 5), indicadas na
tabela. Dadas as condições de montagem da opção i, por
cada sequência de ni carros, só podem ser montadas mi
opções, como indicado na tabela (p. ex., por cada sequência
de 5 carros, só dois podem ter a opção 4 instalada).
opção
1
2
3
4
5
capacidade
1
1/2
X
2/3
1/3
X
2/5
X
1/5
Configuração 1
2
3
4
carros
5
6
7
8
X
X
X
9
10
X
X
X
X
2
X
X
3
4
5
6
61
Restrição Global - Sequência
Pretende-se pois implementar de forma eficiente uma
restrição gsc/7 (global sequencing constraint)
gsc(X, V, Seq, Lo, Up, Min, Max)
A sua semântica é a seguinte:
Dada a sequência de variáveis X, Min e Max representam o
número mínimo/máximo de vezes que elas podem tomar
valores no conjunto V. Adicionalmente, em cada sequência
de Seq variáveis, Lo e Up representam o número
mínimo/máximo de vezes que elas podem tomar valores no
referido conjunto V.
De notar que em CHIP a restrição gsc/7 tem sintaxe
among([Seq, Lo, Up, Min, Max ], X, _, V).
62
Restrição Global - Sequência
opção
1
2
3
4
5
capacidade
1
1/2
X
2/3
1/3
X
2/5
X
1/5
Configuração 1
2
3
4
carros
5
6
7
8
X
X
X
9
10
X
X
X
X
2
X
X
3
4
5
6
golo(X):X = [X1, .. ,X10], L :: 1..6,
gcc(X, L, [1,1,2,2,2,2], [1,1,2,2,2,2]),
gsc(X, [1,5,6], 2, 1, 1, 5, 5),
gsc(X, [3,4,6], 3, 2, 2, 6, 6),
gsc(X,
[1,5] , 3, 1, 1, 3, 3),
gsc(X, [1,2,4], 5, 2, 2, 4, 4),
gsc(X,
[3]
, 5, 1, 1, 2, 2).
63
Restrição Global - Sequência
Dada as semelhanças entre as restrições, foi proposta em
[RePu97] uma implementação eficiente da restrição de
sequênciação gsc/7 a partir da restrição de cardinalidade
gcc/4.
A explicação desta implementação pode ser dada através
de um exemplo.
Dada a sequência X = [X1 .. X15], com X :: 1..4, pretende-se
garantir que os valores [1,2] apareçam entre 8 e 12 vezes e
que cada sequência de 7 variáveis contenha entre 4 e 5
vezes esses valores.
gsc(X, [1,2], 7, 4, 5, 8, 12)
64
Restrição Global - Sequência
gsc(X, [1,2], 7, 4, 5, 8, 12)
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
Xi
1 2 1 3 1 2 3 4 2 3 1 1 2 2 4
Ai
v v v a1 v v a1 a2 v a2 v v v v a3
Começamos por considerar um novo conjunto de variáveis,
Ai, distribuidos em sub-sequências S1, S2 e S3 de 7
elementos (excepto a última). Os valores de um Ak que
pertence à sequência Sk é definido da seguinte maneira
Vi  [1,2]  Ai = v , Vi  [1,2]  Ai = ak
Como é fácil de ver, não podem existir menos de 2 nem
mais de 3 valores a1 e a2 em toda a sequência A, para se
garantirem entre 4 e 5 valores [1,2] em S1 e S2 .
65
Restrição Global - Sequência
gsc(X, [1,2], 7, 4, 5, 8, 12)
gsc(X, V , Seq, Lo, Up, Max, Min)
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
Xi
1 2 1 3 1 2 3 4 2 3 1 1 2 2 4
Ai
v v v a1 v v a1 a2 v a2 v v v v a3
Na sequência S3 tem de existir pelo menos 0 a3 (pode ser
completada à esquerda com suficientes vs) e no máximo 1
a3 para se garantir um número adequado de valores [1,2].
Em geral para sequências de S  Seq valores é necessário
garantir um número de ak , # ak, entre
maximum(0, minimum(S,Seq)- Up) 
# ak  Seq - Lo
66
Restrição Global - Sequência
gsc(X, [1,2],
gsc(X,
1
V
2
3
7
,
4,
5,
8,
12)
, Seq , Lo, Up, Max, Min)
4
5
6
7
8
9
10 11 12 13 14 15
Xi
1 2 1 3 1 2 3 4 2 3 1 1 2 2 4
Ai
v v v a1 v v a1 a2 v a2 v v v v a3
É ainda necessário garantir a existência de entre 8 e 12 vs
(isto é, entre Min e Max) na sequência dos Ai.
Todas estas condições são garantidas, com as restrições
que mapeiam os Xis nos Ais, e ainda com a restrição de
cardinalidade
gsc(A, [v,a1,a2,a3], [8,2,2,0], [12, 3, 3, 1])
67
Restrição Global - Sequência
Nem todas as sequências de 7 (Seq) elementos foram
ainda consideradas. Para esse efeito, teremos de
considerar 7 (Seq) restrições gcc, como indicado no
seguinte esquema
1
Xi
2
3
4
5
6
7
8
9
10 11 12 13 14 15
1 2 1 3 1 2 3 4 2 3 1 1 2 2 4
Ai
a1
a1 a2
a2
a3
Bi
b2
b2 b2
b3
b3
Ci
c2
c2 c2
c3
c4
Di
d2
d2 d2
d2
d3
Ei
e1
e2 e2
e2
e3
Fi
f1
f2 f2
f2
f3
Gi
g1
f2 f2
f2
f3
68
Restrição Global - Sequência
A restrição gsc é pois mapeada em 7 restrições gcc
Xi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
2
1
3
1
2
3
4
2
3
1
1
2
2
4
Ai
a1
a1 a2
a2
a3
Bi
b2
b2 b2
b3
b3
Ci
c2
c2 c2
c3
c4
Di
d2
d2 d2
d2
d3
Ei
e1
e2 e2
e2
e3
Fi
f1
f2 f2
f2
f3
Gi
g1
f2 f2
f2
f3
gsc(A,
gsc(B,
gsc(C,
gsc(D,
gsc(E,
gsc(F,
gsc(F,
[v,a1,a2,a3],
[v,b1,b2,b3],
[v,c1,c2,c3],
[v,d1,d2,d3],
[v,e1,e2,e3],
[v,f1,f2,f3],
[v,f1,f2,f3],
[8,2,2,0],
[8,0,2,2],
[8,0,2,1],
[8,0,2,2],
[8,0,2,0],
[8,0,2,0],
[8,1,2,0],
[12,3,3,1])
[12,1,3,3])
[12,2,3,3])
[12,3,3,3])
[12,3,3,3])
[12,3,3,3])
[12,3,3,2])
69
Restrição Global - Stretch
Recentemente [Pesa01] foi proposta uma restrição global
stretch que pretende considerar globalmente situações em
que se pretende “esticar” as sequências de valores iguais
para variáveis consecutivas.
A sua utilização é descrita para problemas de horários de
escalas de pessoal. Por exemplo, garantir que uma
enfermeira tenha uma sequência máxima de turnos
diurnos, e não uma alternância de turnos diurnos e
nocturnos.
Naturalmente, esta restrição global deve ser integrada
num contexto de outras restrições e permitir uma
filtragem eficiente de valores que não seria possível obter
através da formulação dessa restrição por um conjunto de
restrições mais simples.
70