Constraint Logic Programming
[email protected]
http://www.knoesis.org/tkprasad/
cs7120 (Prasad)
L23-CLP
1
Ordinary Logic Programming
?- p(a,X) = p(Y,b).
Y=a
X=b
?- p(X,X) = p(a,b).
*fails*
• Unification solves equality constraints
(under unique name hypothesis)
cs7120 (Prasad)
L23-CLP
2
Constraint Logic Programming
?- X + 2 = 5.
*fails in ordinary LP*
In CLP, succeeds with: X = 3
• Generalizes to constraint satisfaction
problem, interpreting “+” as the arithmetic
addition operator
cs7120 (Prasad)
L23-CLP
3
Constraint Satisfaction Problem
• Given a set of variables, their types (domains of
values and applicable operations), and constraints
on them, determine assignment of values to
variables so that the constraints are satisfied.
• Benefit: Embodiment of Declarative
Programming
• Challenge: Designing tractable constraint
languages
cs7120 (Prasad)
L23-CLP
4
Applications
• Scheduling and Resource Management in
production and transportation
• teachers and courses to class rooms
• machines to jobs
• crews to planes
• Linear and Non-linear programming
problems
• Mortgage Calculations
cs7120 (Prasad)
L23-CLP
5
CLP : Motivation
fib(0,1).
fib(1,1).
fib(N,X) :- N1 is N-1, N2 is N-2,
fib(N1,X1), fib(N2,X2),
X is X1 + X2.
?- fib(4,5).
Succeeds.
?- fib(X,5).
Fails.
• Treatment of arithmetic expression looks unnatural as it
does not smoothly integrate with the logic programming
paradigm (e.g., invertibility destroyed)
cs7120 (Prasad)
L23-CLP
6
Introducing the Theory of Arithmetic
fib(0,1).
fib(1,1).
fib(N, X1 + X2) :- N > 1,
fib(N - 1,X1), fib(N - 2,X2).
• Interpret arithmetic operators in the domain of reals
– improves readability
– improves invertibility
?- fib(N, 13).
N = 6.
?- fib(N, X), 10 =< X, X =< 25.
N = 6. X = 13.
N = 7. X = 21.
cs7120 (Prasad)
L23-CLP
7
Solving Simultaneous Equations
?- X + Y = 12, 2*X + 4*Y = 34.
X = 7. Y = 5.
• Complex Multiplication
zmul(c(R1,I1),c(R2,I2),c(R3,I3)) :R3 = R1 * R2 - I1 * I2,
I3 = R1 * I2 + R2 * I1.
?- zmul(c(2,2),Ans,c(0,16))
Unique solution:
Ans = C(4,4)
?- zmul(A,B,c(0,16))
Infinite solution:
*Set of constraints*
cs7120 (Prasad)
L23-CLP
8
Prolog vs CLP(R)
?- 5 + 2 = X + Y. ?- 5 + 2 = X + Y.
X = 5 Y = 2
X = 7 - Y
?- 5 + 2 = X + 3. ?- 5 + 2 = X + 3.
*fail*
X = 4
• Equality constraints over
terms
cs7120 (Prasad)
• General constraints over
arithmetic expressions;
Equality constraints over
terms
L23-CLP
9
Prolog vs CLP(R)
• Uninterpreted function
symbols
• Arithmetic operators +
uninterpreted term trees
• General constraint
solvers
• Unification algorithm
– E.g., Simplex algorithm
for linear constraints
• Backtrack when terms fail
to unify
cs7120 (Prasad)
• Backtrack when
constraints violated
L23-CLP
10
CLP : Linear Programming
light_meal(A,M,D) :- appetizer(A,I),
main_course(M,J),
dessert(D,K),
I >= 0, J >= 0, K >= 0,
I + J + K <= 12.
appetizer(soup,1).
appetizer(nachos,6).
main_course(sphagetti,3).
main_course(alfredo,7).
dessert(fruit,2).
dessert(ice_cream,6).
cs7120 (Prasad)
L23-CLP
11
?- light_meal(App,Main,Dess).
Dess = fruit
Main = sphagetti
App = soup
*** Retry? y
Dess = ice_cream
Main = sphagetti
App = soup
Dess = fruit
Main = alfredo
App = soup
*** Retry? y
Dess = fruit
Main = sphagetti
App = nachos
*** Retry? y
cs7120 (Prasad)
L23-CLP
12
CLP : Mortgage Payment Calculator
%mortgage(Principal, Time_Months,
Interest_Rate, Monthly_Payment,
Balance)
mortgage(P,0,_,_,P).
mortgage(P,1,I,MP,B) :B = P * (1 + (I / 1200)) - MP.
mortgage(P, T, I, MP, B) :mortgage( (P * (1 + I / 1200)) - MP,
T – 1, I, MP, B).
cs7120 (Prasad)
L23-CLP
13
CLP : Mortgage Payment Queries
%mortgage(Principal, Time_Months,
Interest_Rate, Monthly_Payment,
Balance)
%Customer: What will be the monthly payment?
?- mortgage(148000,180,8,M,0).
M = 1414.37
%Lender: How much loan does one qualify for, given
monthly payment limit?
?- mortgage(P,180,8,1200,0).
P = 125569
cs7120 (Prasad)
L23-CLP
14
(cont’d)
%mortgage(Principal, Time_Months,
Interest_Rate, Monthly_Payment,
Balance)
%Customer/Lender: What is the remaining balance?
?- mortgage(148000,180,8.375,1124.91,B).
B = 115088
%Customer: How long will it take to clear the debt?
?- mortgage(148000,L,8.5,1400,0).
L = 195.731
cs7120 (Prasad)
L23-CLP
15
(cont’d)
%mortgage(Principal, Time_Months,
Interest_Rate, Monthly_Payment,
Balance)
%Customer: What is the contribution to the principal in the
first month (in a 15 yr loan at 8 or a 30 yr loan at 8.375)?
%Customer: Building equity.
?- mortgage(148000,1,8,1414,148000-CP).
CP = 427
?- mortgage(148000,1,8.375,1124,148000-CP).
CP = 92
cs7120 (Prasad)
L23-CLP
16
Non-linear constraints :
CLP(R) Fails Here
%mortgage(Principal, Time_Months,
Interest_Rate, Monthly_Payment,
Balance)
%Customer: What is the maximum interest rate for the given
principal and monthly payment?
%Customer: Affordability
?- mortgage(148000,180,I,1400,0).
*lots of constraints output*
cs7120 (Prasad)
L23-CLP
17
CLP : Annuity Calculator
%annuity( Time_Months,
Interest_Rate, Monthly_Payment,
Initial_Principal, Total_Value)
annuity(0,_,_,IP,IP).
annuity(T, I, MP, IP, TV) :annuity(T-1, I, MP, IP, V),
TV = MP + (V * (1 + I / 1200)).
cs7120 (Prasad)
L23-CLP
18
CLP : Annuity Queries
%annuity( Time_Months,
Interest_Rate, Monthly_Payment,
Initial_Principal, Total_Value)
%Customer: What will be the final investment value?
?- annuity(180,5,225,0,FV).
FV = 60140
%Customer: What is the net gain?
?- annuity(180,5,225,0,225*180 + G).
G = 19640
cs7120 (Prasad)
L23-CLP
19
CLP : Limitations
?- (Cows + Pigs + Sheeps) = 100,
(10*Cows + 3*Pigs + Sheeps/2) = 100,
Cows >= 1, Pigs >= 1, Sheeps >= 1.
Pigs = -1.35714*Sheeps + 128.571
Cows = 0.357143*Sheeps - 28.5714
Sheeps <= 94
* Lots of constraints *
• CLP(R) is unable to determine the unique solution:
Cows = 5, Pigs = 1, Sheeps = 94
cs7120 (Prasad)
L23-CLP
20
Descargar

Logic Programming - Wright State University