Programação com Constraints
Programando com Constraints
• Linguagens tradicionais (incl. OO): pouco suporte p/
relacionamentos entre objetos
• Ex. V=RxI: vários comandos p/ sit. diferentes
– V:=I*R
– I:=V/R
– R:=V/I
• Constraint Solvers: algoritmos eficientes capazes de verificar exist.
de solução (ex. simplex p/ ineq. lineares)
• Principais áreas de aplicação:
– planejamento
– escalonamento
– otimização
Constraint Logic Programming
• Program. declarativa: Ex. Prolog
– flexibilidade no uso, MAS
– Prolog puro tem apenas unificação
• relações explícitas
• relações obtidas com busca
• relações extra-lógicas (ex. aritméticas) testadas só qdo.
variáveis estão instanciadas
• Idéia: mesclar busca e resolução com “constraints”
• Alternativa seria geração e teste
– ineficiente
– às vezes impossível. Ex. Reais
• Constraint Solver é ativado qdo.
– Constraint é adicionada
– Variável é instanciada
• Impossibilidade de satisfação: árvore de busca é podada 
backtracking
• Obs: o próprio processo de unificação pode ser encarado como uma
resolução de “constraints”
Constraints
•
•
•
•
•
•
Variáveis: repres. valores desconhecidos: X,Y,Z, LIST,...
Símbolos de funções: mapeamento entre valores: +, -, *, /, sen, cos
Símbolos de relações: relações entre valores: =,, 
Constraint Primitiva: Relação com argumentos. Exs. X4 e X+2Y=9
Constraint: conjunção de constraints primitivas: X3  X=Y  Y 4
Valoração: atrib. de valores a variáveis.
–  = { X3, Y 4, Z 2}
– (X+2Y)=3+2*4=11
• Solução: valoração que satisfaz constraint:
(X  3  Y=X+1)=(3  3  4=3+1) = true
• Constr. pode ser satisfeita (satisfiable). Ex. X  3  Y=X+1
• Constr. não pode ser satisfeita (unsatisfiable) X  3  Y=X+1  Y2
Constraints II
• Sintaxe
– São cadeias de símbolos
– Ordem importa  alguns algoritmos dependem da ordem
X=0Y=1 não é o mesmo que Y=1X=0
• Equivalência de Constraints: mesmo conj. de soluções
– X> 0 e 0<X
– X=1Y=2 e Y=2  X=1
– X=Y+1Y2 e X=Y+1X3
• Modelagem com Constraints: descreve comportamento
idealizado dos objetos no mundo. Exs.
– Leis da Física
– Cronogramas de construção
Modelando c/ Constraints
V 1  I 1  R1
V 2  I 2  R2
V V1  0
V V 2  0
I
V1V 2  0
I  I1  I 2  0
 I  I1  I 2  0
+
+
R2
R1
V
V2
V1
I1
-3_
I2
---
Modelando c/ Constraints
start
TS  0
foundations
TA  TS  7
interior walls
TB  TA  4
exterior walls
TC  TA  3
chimney
TD  TA  3
roof
TD  TC  2
doors
TE  TB  2
tiles
TE  TD  3
windows
TE  TC  3
Satisfação de Constraints
•
•
•
•
•
•
Dada constraint C, há 2 perguntas:
– satisfação: ela tem solução?
– solução: qual a solução, se tiver?
Constraint Solver responde à questão sobre satisfação (mais básica), mas
normalmente tem como subproduto solução (soluções)
Abordagem simplificada: tentar todas as valorações (enumeração)
Enumeração não funciona p/ Reais
Versões mais espertas são usadas p/ domínios finitos
Constraints sobre Reais (expressões lineares): métodos de eliminação. Ex.
Gauss-Jordan
– Substit. repetidas de var. p/ colocar eq. em forma x = e
– Forma resolvida: vars. do lado esq.(não-paramétricas) não aparecem no
lado direito de nenhuma eq.
– partindo de 1+X=2Y+Z  Z-X=3 X+Y=5+Z
chegar em conclusão de não-satisfação
– Usando só 2 prim. eqs.: X=Z-3  Y=-1
– Atribuindo valores arbitrários p/ parâmetros, obtêm-se valores das demais
variáveis.
Domínios
• Inteiros
• Reais
• Igualdade de árvores: unificação de termos
(como no Prolog)
• Valores Booleanos
• Constraints sobre seqüências. Ex. Genética
• Mundo dos blocos: constraints não têm que ser
matemáticas
• Muitos outros: normalmente relacionados a
estruturas matemáticas bem conhecidas.
Valores Booleanos
•
Ex. de uso em modelagem de
X
O
circuitos
•
•
•
Valores 0 e 1
Álgebra de Boole
Operação E representada por
“&” p/ não confundir com
composição de constraints
• Ex. 1: XOR com máx. 1 falha
• Valor observado:
• { X 0, Y  0, Z  1}
• Solução
{ FO  1, FA  0, FN  0,
FZ  0, X 0, Y  0, Z  1}
Z
Y
A
FO  (O  (XY))
FA  (A  (X&Y))
FN  (N  A)
FZ  (Z  N&O)
(FO&FA)  (FO&FN) 
(FO&FZ)  (FA&FN) 
(FA&FZ)  (FN&FZ)
N
Valores Booleanos
• Vários métodos
• P/ ser completo: complex. exponencial (problema NP)
• Método incompleto, mas útil (c/ tempo polinomial)
– Seja m o núm. de constraints primitivas em C, seja epsilon
um número entre 0 e 1 (grau do quão incompleto deve ser o
algoritmo)
– Para i =1 até n
• Gere uma valoração randômica das variáveis em C
• Se valoração satisfaz C, então retorne true
– Retorne não sei
Propriedades de CS
• Completo. Desejável, mas muitas vezes não
existe (ex. eq. não-lineares sobre inteiros) ou
demora muito (ex. booleanas, eqs. não lin.
sobre reais)
• Bem comportado
– Baseado em conjunto: resposta depende apenas do
cj. de constr. primitivas
– Monotônico falha p/ C1  falha p/ C1  C2
– Independente do nome das variáveis: renomeandose variáveis obtém-se mesmo resultado
Simplificação de Constraints
• Constraints podem ser equivalentes, mas uma mais simples que a
outra
X1X 3  2=X+Y
X  3  2=X+Y 
3X X=2-Y 
X=2-Y  3X 
X=2-Y  3  2-Y 
X=2-Y  Y  -1
• Oper. que mantêm equivalência
–
–
–
–
rem. de constraints redundantes
reescrita de constraint primitiva
mudança de ordem
substituição usando equação
Projeção
• Simplificação importante: interesse em apenas algumas variáveis,
por exemplo p/ expressar resultado
• A projeção de uma constraint C no cj. de variáveis V é uma
constraint C1 tal que
– C1 tem apenas variáveis de V
– Toda solução de C é sol. de C1
– Uma sol. de C1 pode ser estendida de forma a produzir sol. p/ C
C: XY  YZ  Z  0 tem como proj. em {X}
C1: X  0
{ X 0} em C1 pode ser estendida p/ { X 0, Y  0, Z  0} em C
{ X 4, Y  3, Z  1} em C é sol de C1, porque { X 4 } já é sol.
• Algoritmo de Fourier p/ elimin. de var. Y
–
–
–
–
divisão de ineqs. em t1Y e Y t2 e outras
casar pares p/ produzir ineqs. t1 t2
aplicável tb. p/ ineq. estritas (“<” e “>”)
pode produzir inform. redundante a ser filtrada
Projeção II
• Exemplo de alg. de Fourier, excluindo Y (projetando em apenas {X})
X 1 Y
Y
 1 X  Y
Y  1 X
Y  1 X
X  1  Y  Y  1 X
+1
-1
+1
X
+1
X
X 1
X 1  Y  Y  1 X 0  2
 1 X  Y  Y  1 X 0  2
 1 X  Y  Y  1 X  1  X
-1
-1
X  1  1  X
• Obs.: não são todos os domínios que possibilitam projeção: às
vezes são criadas variáveis locais p/ expressar relações
Otimização e Verific. de Implicação
• Problemas de otimização
– achar valor mínimo p/ função, dado cj. de constraints
– P/ ineq. lineares, Fourier pode ser usado, mas é ineficiente
– Simplex:
• tempo polinomial na prática
• fornece algoritmo eficiente p/ verificação da satisfação de
constraints
• Verificação de implicação e equivalência
– Pode-se usar implic. p/ definir equivalência e vice-versa
impl(C1,C2)=equiv(C1,C1C2)
equiv(C1,C2)=impl(C1,C2) impl(C2,C1)
– pode-se usar constraint solver p/ testar implicação
impl(C1,C2)=¬solv(C1 ¬C2)
– ex.
• impl(CH,TBTC)= ¬solv(CH  TB<TC)
Implementações
• Cada constraint solver tem sua sintaxe. Para o uso de cada um,
normalmente inclui-se um módulo.
• Constraint solvers no SWI: clpq(racionais), clpr (reais) e
‘clp/bounds’ (domínio finito) e simplex
• Constraint solvers no SICSTUS: clpq(racionais), clpr (reais) e
‘clpfd’ (domínio finito) e clpb (booleanos)
Ex. Hipoteca
:-use_module(library(clpr)).
mortgage(P,T,I,R,B):- {T=0, P=B}.
mortgage(P,T,I,R,B):{
T>=1.0,
NT=T-1,
NP=P+P*I-R
},
mortgage(NP,NT,I,R,B).
• P: principal, T: tempo, I: juros, R: prestação, B: saldo
• Vários usos
– mortgage(1000,10,10/100,150,B). Resp: B=203.129
– mortgage(P,10,10/100,150,0). Resp: P=921.685
– mortgage(P,10,10/100,R,B). Resp: P=0.3855*B+6.1446*R
Relação entre principal, saldo e prestação
• Note: indicação de uso do módulo e constraints entre “{“ e “}” (para reais)
Referências
• Prolog c/ constraints
– Eclipse: consórcio europeu, grupo agora no Imperial College
– Sicstus Prolog: constraint solvers p/
• booleanos
• racionais
• reais
• domínios finitos
– CHR: biblioteca para criação de “constraint solvers”
– Livro base: Programming with Constraints: An Introduction.
Marriott and Stuckey (1998)
– Conferência Principal: Principles and Practice of Contraint
Programming (CP)
– Pesquisas e desenvolvimentos relacionados
• Bancos de Dados com constraints
• Outros paradigmas de linguagens c/ Constraints: funcionais,
imperativas e OO