Constraint Logic Programming

1Chapter 4Constraint Logic Programming2OutlineIntroductionThe constraint logic programming schemeCLP languages and applicationsCLP(R)CHIPB-PrologConclusions3IntroductionGiven a particular domain, a constraint expresses a desired relationship among one or more of the objects. Many practical problems can be regarded as constraint satisfaction problems (CSPs).Logic Programming (LP) languages such as Prolog, with their general purpose Horn clause represen-tation and single clear semantics, are very good at expressing constraints in a declarative fashion. However, Prolog’s unification mechanism is not sufficiently powerful to handle constraints properly.Unification is not good at processing constraints non-deterministically.4Limitation of PrologExample 1:plus(X,Y,Z) :- Z = X+Y.It is unable to deal satisfactorily with: ?- plus(X,Y,2).Example 2:fact(0,1).fact(N,F):- N>0, N1 is N -1, fact(N1,F1), F is N*F1.The query ?- fact(2,F). gives the answer F = 2,but Prolog fails with the query ?- fact(N,2).5CLP = logic Programming + Constraint ProgrammingThere has been some effort within the Logic Programming community to extend Prolog to overcome these limitations with unification.However, despite these improvements, LP language still suffer from significant efficiency problems when dealing with constraint satisfaction. Their simple backtracking search method implies a generate-and-test procedure in which variable values are generated and the constraints are used passively to check the values.Recently, there has been a radical approach at extending the Logic Programming paradigm to produce Constraint Logic Programming (CLP) languages. CLP is a merger of two declarative paradigms: constraint programming and logic programming. 6Improvements of CLPLike Logic Programming, CLP uses the resolution principle. However, unification has been replaced by constraint solving over an application domain.CLP improves on Logic Programming when dealing with constrained search problems, by providing:more expressive languages in which a user can work directly with objects from the intended domain and employ the natural constraints for that domain, andfar more efficient execution employing specialized methods and algorithms.7THE CONSTRAINT LOGIC PROGAMMING SCHEME Jaffar and Lassez have given the formal definition of a class of languages for which there is a simple and unified declarative and operational semantics. This is a general framework from which many CLP languages can be derived. Each instance of this scheme is obtained by specifying a solution-compact structure of computation.A structure A consists of: a set D(A) – the domain of A a collection  of n-ary function: An  A; a collection  of n-ary relations: An  {TRUE, FALSE}.An A-term is either a constant in ; a variable; or of the form f(X1,,Xn) where f is a function and the Xi are A-terms.8An constraint is of the form: p(X1,,Xn) where p  and the Xi are A-terms An atom is of the form: p(X1,,Xn) where p is a predicate symbol  and the Xi are A-terms.Countable structures, the structure of real numbers are solution-compact.By specifying a solution-compact structure A, one obtains a programming language CLP(A) which is an instance of the CLP Scheme.9A CLP(A) program consists of a finite number of rules: A0 :- C1, C2,,Cn, A1, A2,,Amwhere n, m  0, Ci are constraints over the A-relations and A-terms, Ai are atoms over the A-terms.A CLP(A) goal is of the form: ?- C1, C2,,Cn, A1, A2,,Amwhere n, m  0, n+m  1, Ci are constraints Ai are atomsAn atom in a goal is a subgoal.If A, B are two atoms with the same predicate symbol, A = B is used to signify the collection of equations between corresponding arguments in these two atoms. Example:If A is resistor(X,Y, 5) and B is resistor(2,8,Z),Then A = B denotes { X = 2, Y = 8, Z = 5}.10The CLP(A) Operational ModelLet P denote a CLP(A) program. Let G1, G2 be two goals containning the collections C1, C2 of constraints. Assume that both C1 and C2 are solvable.There is a derivation step from G1 to G2 if:  G1 is of the form ?- C1,A1,A2,,Am, where m>= 1  P contains a rule of the form B0 :- C2,D1,D2,,Dk. where k >= 0 ( B0 can match with Ai).  G2 is of the form ?- C1,C2, Ai = B0, A1,A2,Ai-1,Ai+1,,Am, D1,D2,,Dk where 1  i  mAi in G1 is called the selected subgoal, or the subgoal in G1 chosen to be reduced.11A derivation sequence is a sequence of goals in which there is a derivation step to each goal from the preceding goal.A derivation sequence is successful if it is finite and its last goal contains only constraints. Such constraints are called answer constraints. Answer constraints constitute the output of a CLP(A) program.A finitely-failed sequence is a non-successful finite sequence, where no derivation step is possible from its last goal.A CLP(A) program and goal are executed by a process of continually reducing any remaining atoms in the subgoal.12A comparison of CLP to LPLogic Programming Constraint Logic Programming Domain of computationHerbrand Universe of uninterpreted terms Any solution compact structure syntax syntax Horn clauses Horn clauses Horn clauses with constraints operational interpretation unification and resolutionconstraint solving and resolution output mgua set of constraints 13CLP LANGUAGES AND APPLICATIONS In this section, we look at some of the best-known and most successful implementations of the CLP schema.The design and implementation of constraint solvers for these languages has been of key important:efficiency in dealing with simple constraints, which are the most commonly occurring.incrementality, so that solving extra constraints does not involve re-solving the original set.an internal representation facilities efficient backtracking.We will study 3 languagesCLP(R)CHIPB-Prolog14CLP() CLP() was developed by Jaffar and Michaylov at IBM, Yorktown Heights and at Monash University, Australia. The domain of computation: reals.Real constants and variables are arithmetic terms. If t1, t2 are arithmetic terms, then so are (t1+t2), (t1-t2), (t1*t2) and (t1/t2). Arithmetic terms, uninterpreted constants and variables are all terms. If f is an n-ary uninterpreted function and t1,,tn are terms, then so the tree t(t1,,tn).An equation or inequality between arithmetic terms is an arithmetic constraint, solvable when there exists a substitution for its variables that makes it true in the obvious way. Two trees are equal when they share the same root function and the corresponding subtrees are equal.15The CLP() interpreter The CLP() interpreter:employs the Prolog’s left-to-right atom selection rule.employs Prolog’s top-to-bottom depth-first-search strategy.Its constraint solver does not determine the solvability of all linear non-constraints. The determination of constraint solvability may be delayed until the constraint is “sufficiently instantiated”. In CLP(), a non-linear constraint c is delayed until the linear equations in the system entail that sufficient variables in c are ground, so as to make it linear. When a delayed constraint is awoken and found to be unsolvable, the system backtracks as in Prolog. The delaying and awakening process is automatic and is designed to be transparent to the user.16InputEngineInterfaceSolve directlyEquation SolverInequation SolverdelaySolve directlyOutputModuleCONSTRAINTSOLVERThe architecture of the CLP(R) interpreter17The inference engine controls the execution of derivation steps and maintains variable bindings. Some simpler constraints can be solved directly by the engine. The remainder is passed on the interface, which will eventually return a Boolean answer to the engine. The interface evaluates complex arithmetic expression and transforms constraints into a small number of standard forms. It can do some constraint satisfaction of its own, but in the main, passes on the standardized constraints to the constraint solver.The constraint solver lets the equation solver deal with linear equations, using a form of Gaussian elimination. It calls the inequality solver to handle linear inequalities, using an incremental form of the first phase of the Two-phase Simplex method. It delays non-linear equation, awakening them when they become linear and then passing them to the equation solver. 18The output module converts constraints so that they reflect relationships only between variables in the goal, and transform these into a compact standard canonical form.Example Programs: fib(0,1). fib(1,1). fib(N+2, X +Y):- N>= 0, fib(N+1, X), fib(N,Y).Steps in the computation of the goal fib(N0,3) are as follows:19?- fib(N0,3).?- N1 >= 0, N0 = N1 + 2, 3 = X1 + Y1, fib(N1+1, X1), fib(N1,Y1).?- N1 >= 0, N0 = N1 + 2, 3 = X1 + Y1, N2 >= 0, N1 + 1 = N2 +2, X1 = X2+Y2, fib(N1, Y1), fib(N2+1, X2), fib(N2,Y2).?- N1 >= 0, N0 = N1 + 2, 3 = X1 + Y1, N2 >= 0, N1 + 1 = N2 +2, X1 = X2+Y2, N1 = 1, Y1 = 1, fib(N2+1, X2), fib(N2,Y2).?- N1 >= 0, N0 = N1 + 2, 3 = X1 + Y1, N2 >= 0, N1 + 1 = N2 +2, X1 = X2+Y2, N1 = 1, Y1 = 1, N2+1=1, X2=1, fib(N2,Y2).?- N1 >= 0, N0 = N1 + 2, 3 = X1 + Y1, N2 >= 0, N1 + 1 = N2 +2, X1 = X2+Y2, N1 = 1, Y1 = 1, N2+1=1, X2=1, N2=0,Y2=1.Solving the final constraint set, with respect to N0, we obtain: N0 = 3.20Electrical CircuitCLP() program for selecting components in an electrical circuit.ohmlaw(V, I, R):- V = I*R.kirchoff(L):- sum(L,0).sum([ ],0).sum([H|T], N):- N = H+M, sum(T,M).availres(10).availres(14).availres(27).availres(60).availres(100).availcell(10).availcell(20).21and the query: ?- 14.5= 3, X12 + X22 >= 5, X13 + X23 >= 2, X11 + X12 + X13 = Si + diExample. The following table describes a project with 10 tasks A, B, C, D,E, F, G, H, J, and K. 43Code of the taskName of the task Duration (in weeks) Previous tasks AMasonry 7-BCarpentry for roof 3ACRoof 1BDSanitary and electrical installation 8AEFront 2D,CFWindows 1D,CGGarden 1D,CHCeiling 3FJPainting 2HKMoving in 1E, G, J44/* Title : House building scheduling problem *//* House building scheduling problem with 10 tasks */house(L):- L =[SA,SB,SD,SC,SE,SF,SG,SH,SJ,SK,Send], L in 0..30, SB #>= SA+7, SD #>= SA+7, SC #>= SB+3, SE #>= SC+1, SE #>= SD+8, SG #>= SC+1, SG #>= SD+8, SF #>= SD+8, SF #>= SC+1, SH #>= SF+1, SJ #>= SH+3, SK #>= SG+1, SK #>= SE+2, SK#>= SJ+2, Send #>= SK+1, minof(labeling(L),Send).45Note: 1.The variables SA,,SK represent the starting dates of the tasks of the project, and the Send is the starting date of the end task, i.e., the finishing date.2.The predicate minof(Goal, Exp) finds a satisfiable instance of Goal such that Exp has the minimum optimal value. Here, Goal is used as generator (e.g., labeling(L)), and Exp is an expression. All satisfiable instances of Goal must be created, and for every such instance, Exp must be an integer expression.In B-Prolog, the search for an optimum solution uses a kind of depth-first branch and bound technique. 46For example, when a solution with a value F0 is found, the constraint (Goal < F0) is dynamically added to the program. While searching a new solution, all branches of the search space where the value of Goal is greater than F0 are pruned. The optimal solution is achieved when no new solution better than the most recent one can be found. ?- house(LD). LD = [0,7,7,10,15,15,15,16,19,21,22]. That means SA = 0, SB = 7, SC=7, SD = 10, SE=15, SF=15, SG=15, SH=16, SJ=19, SK=21, Send = 22.47Example 7: Project selection A company is considering expansion by building a new factory in either city L or city S, or perhaps in both cities. It also is considering building at most one new warehouse, but the choice of location is restricted to a city where a new factory is being built. The net present value (total profitability) of each of these alternatives is shown in the fourth column of the following table.DecisionNumber Yes-or-No Question DecisionVariable Net PresentValue Capital Required 1 Build factory in L x19 M6M2Build factory in S x25 M3 M3Build warehouse in L x36 M5 M4Build warehouse in Sx44 M2 M48Project selection (cont.)Capital available: 10 millionThe rightmost column gives the capital required for the respective investments. The total capital available is 10 million. The objective is to find the feasible combination of alternatives that maximizes the total net present value.Because the last two decisions are mutual exclusive, we need the constraint x3 + x4  1Furthermore, decision 3 and 4 are contingent decisions, because they are contingent on decisions 1 and 2. x3  x1 x4  x2.49projs(L):- L= [D1,D2, D3,D4], L in 0..1, 6*D1 +3*D2+5*D3+2*D4 #=< 10, D3 + D4 #=< 1, D3 #=< D1, D4 #=< D2, maxof(labeling(L), 9*D1+5*D2 + 6*D3+4*D4). ?- projs(L). L = [1,1,0,0]That means the company should build factories in both cites but no warehouse.50Example 8: Assignment Problem The assignment problem is a problem where assignees are being assigned to perform tasks. For example, the assignees might be employees who need to be given work assignments. However, the assignees could be machines, or vehicles or plants. To fit the definition of an assignment problem, the applications need to be formulated in a way that satisfies the following assumptions.The number of assignees and the number of tasks are the same. (This number is denoted by n.)Each assignee is to be assigned to exactly one task.Each task is to be performed by exactly one assignee.There is a cost cij associated with assignee i (i = 1,2,,n) performing task j (j =1,2,,n).The objective is to determine how all n assignments should be made in order to minimize the total cost.51Example: A company has purchased 3 new machines of different types. There are 4 available locations in the shop where a machine could be installed. Some of these locations are more desirable than others. Therefore, the objective is to assign the new machines to the available locations to minimize the total cost of material handling. The estimated cost per unit of material handling involving each of the machines is given in the following table. Task 1 2 3 4 1 13 16 12 11 2 15 M 20 13Machine 3 5 7 0 0 4(D) 0 0 0 0 An very large cost M is attached to the assign-ment of machine 2 to location 2 to prevent this assignment in the optimal solution. 52We must introduce a dummy machine to the extra location.assign(L):- L=[X11,X12,X13,X14,X21,X22,X23,X24, X31,X32,X33,X34,X41,X42,X43,X44], L in 0..1, X11+X12+X13+X14 #=1, X21+X22+X23+X24 #=1, X31+X32+X33+X34 #=1, X41+X42+X43+X44#=1, X11+X21+X31+X41 #=1, X12+X22+X32+X42 #=1, X13+X23+X33+X43 #=1, X14+X24+X34+X44 #=1, minof(labeling(L), 13*X11+16*X12+12*X13+11*X14 + 15*X21 +1000*X22 + 13*X23 + 20*X24+ 5*X31 + 7*X32 + 10*X33 + 6*X34).?- assign(L).L =[0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0]X14 = 1, X23 = 1, X31= 1, X42 = 1That means: machine 1 is assigned to location 4, machine 2 to location 3, machine 3 to location 1.53CONCLUSIONS CLP extends unification to constraint solving in new computation domains richer than the usual Herbrand universe.CLP allows building the systems that combine logic and mathematical techniques – qualitative and quantitative, symbolic and numeric, heuristics and algorithm. The programmer can reason directly in term of the intended domain, instead of being forced to code semantic objects in term of a Herbrand universe.The modeling of problems which involves choosing the computation domain, variables, values and constraints, is vital in achieving concise descriptions and efficiency. 54Successful modeling requires a good understanding of the problem, of relevant AI and Operations Research techniques and of the CLP system itself.