clpr: The CPL(R) package

XSB's tabling engine supports the use of attributed variables (Section 1.2), which in turn have been used to port real constraints to XSB under the CLP(R) library of Christian Holzbauer [10]. Constraint equations are represented using the Prolog syntax for evaluable functions (Volume 1, Section 6.2.1). Formally:

		 ConstraintSet -> C     

| C , C   




C -> Expr =:= Expr 		 equation 

| Expr = Expr 		 equation 

| Expr < Expr 		 strict inequation 

| Expr > Expr 		 nonstrict inequation 

| Expr =< Expr 		 nonstrict inequation 

| Expr >= Expr 		 disequation 




Expr -> variable 		 Prolog variable 

| number 		 floating point number 

| + Expr 

| - Expr 

| Expr +  Expr 

| Expr - Expr 

| Expr * Expr 

| Expr / Expr 

| abs(Expr) 

| sin(Expr) 

| cos(Expr) 

| tan(Expr) 

| pow(Expr,Expr) 		 raise to the power 

| exp(Expr,Expr) 		 raise to the power 

| min(Expr,Expr) 		 minimum of two expressions 

| max(Expr,Expr) 		 maximum of two expressions 

| #(Expr) 		 symbolic numerical constants 

The CLP(R) library supports solutions of linear equations and inequalities over the real numbers and the lazy treatement of nonlinear equations. In displaying sets of equations and disequations, the library removes redundancies, performs projections, and provides for linear optimization. The goal of the XSB port is to provide the same CLP(R) functionality as in other platforms, but also to allow constraints to be used by tabled predicates. This section provides a general introduction to the CLP(R) functionality available in XSB, for further information see http://www.ai.univie.ac.at/clpqr.

The clpr package may be loaded by the command [clpr]. Loading the package imports exported predicates from the various files in the clpr package into usermod (see Volume 1, Section 3.3) so that they may be used in the interpreter. Modules that use the exported predicates need to explicitly import them from the files in which they are defined (e.g. bv, as shown below).

{+Constraints}

When the CLP(R) package is loaded, inclusion of equations in braces ({}) adds the equations to the constraint store where they are checked for satisfiability.

     | ?- [clpr].
     [clpr loaded]
     [itf3 loaded]
     [nf loaded]

     yes

     | ?- {X = Y+1, Y = 3*X}.

     X = -0.5000
     Y = -1.5000;

     yes

entailed(Constraint)

Succeeds if Constraint is logically implied by the current constraint store. entailed/1 does not change the constraint store.

| ?- {A =< 4},entailed(A =\= 5).

yes

Note: this predicate does not always work in Version 2.5, due to a bug in cutting over interrupts for attributed variables.

inf(+Expr,-Val)

bv

sup(+Expr,-Val)

bv

minimize(Expr)

bv

maximize(Expr)

bv

These four related predicates provide various mechanisms to compute the maximum and minimum of expressions over variables in a constraint store. In the case where the expression is not bounded from above over the reals sup/2 and maximize/1 will fail; similarly if the expression is not bounded from below inf/2 and minimize/1 will fail.

| ?- {X = 2*Y,Y >= 7},inf(X,F).

X = _h8841
Y = _h9506
F = 14.0000

| ?- {X = 2*Y,Y >= 7},minimize(X).

X = 14.0000
Y = 7.0000

| ?- {X = 2*Y,Y =< 7},maximize(X-2).

X = 14.0000
Y = 7.0000

| ?- {X = 2*Y,Y =< 7},sup(X-2,Z).

X = _h8975
Y = _h9640
Z = 12.0000

yes
| ?- {X = 2*Y,Y =< 7},maximize(X-2).

X = 14.0000
Y = 7.0000

yes

bb_inf(+IntegerList,+Expr,-Inf,-Vertex, +Eps)

Works like inf/2 in Expr but assumes that all the variables in IntegerList have integral values. Eps is a positive number between 0 and 0.5 that specifies how close an element of IntegerList must be to an integer to be considered integral - i.e. for such an X, abs(round(X) - X) < Eps. Upon success, Vertex is instantiated to the integral values of all variables in IntegerList. bb_inf/5 works properly for non-strict inequalities only.

| ?- {X > Y + Z,Y > 1, Z > 1},bb_inf([Y,Z],X,Inf,Vertex,0).

X = _h14286
Y = _h10914
Z = _h13553
Inf = 4.0000
Vertex = [2.0000,2.0000]

yes

bb_inf(+IntegerList,+Expr,-Inf)

Works like bb_inf/5, but with the neighborhood, Eps, set to 0.001.

|?- {X >= Y+Z, Y > 1, Z > 1}, bb_inf([Y,Z],X,Inf)

X = _h14289
Y = _h10913
Z = _h13556
Inf = 4.

yes

dump(+ConstraintSet,+NewVars,-CodedTerm

clpr

(No documentation yet available).