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