Go to the previous, next section.
The clp(Q,R) system described in this document is an instance of the general Constraint Logic Programming scheme introduced by [Jaffar & Michaylov 87].
The implementation is at least as complete as other existing clp(R) implementations: It solves linear equations over rational or real valued variables, covers the lazy treatment of nonlinear equations, features a decision algorithm for linear inequalities that detects implied equations, removes redundancies, performs projections (quantifier elimination), allows for linear dis-equations, and provides for linear optimization.
The full clp(Q,R) distribution, including a stand-alone manual
and an examples directory that is possibly more up to date than
the version in the SICStus Prolog distribution, is available from:
http://www.univie.ac.at/clpqr/.
Holzbaur C.: OFAI clp(q,r) Manual, Edition 1.3.3, Austrian Research Institute for Artificial Intelligence, Vienna, TR-95-09, 1995.
We include a collection of examples that has been distributed with the Monash University version of clp(R) [Heintze et al. 87], and its inclusion into this distribution was kindly permitted by Roland Yap.
You must choose whether you want to operate in the field of Q (Rationals) or R (Reals):
| ?- use_module(library(clpq)). or | ?- use_module(library(clpr)).
clp(q) ?- and clp(r) ?-
are used to differentiate between clp(Q) and clp(R) in exemplary interactions.
In general there are many ways to express the same linear relationship. This degree of freedom is manifest in the fact that the printed manual and an actual interaction with the current version of clp(Q,R) may show syntactically different answer constraints, despite the fact the same semantic relationship is being expressed. There are means to control the presentation, see section Variable Ordering. The approximative nature of floating point numbers may also produce numerical differences between the text in this manual and the actual results of clp(R), for a given edition of the software.
module(linear).
{}/1 with
other solvers, you can avoid its importation via:
use_module(clpq, []).
Constraint --> C
| C , C conjunction
C --> Expr =:= Expr equation
| Expr = Expr equation
| Expr < Expr strict inequation
| Expr > Expr strict inequation
| Expr =< Expr nonstrict inequation
| Expr >= Expr nonstrict inequation
| Expr =\= Expr disequation
Expr --> variable Prolog variable
| number floating point or integer
| + Expr unary plus
| - Expr unary minus
| Expr + Expr addition
| Expr - Expr subtraction
| Expr * Expr multiplication
| Expr / Expr division
| abs(Expr) absolute value
| sin(Expr) trigonometric sine
| cos(Expr) trigonometric cosine
| tan(Expr) trigonometric tangent
| pow(Expr,Expr) raise to the power
| exp(Expr,Expr) raise to the power
| min(Expr,Expr) minimum of the two arguments
| max(Expr,Expr) maximum of the two arguments
| #(Const) symbolic numerical constants
Conjunctive constraints {C,C} have been made part of the syntax
in order to enable grouped submission of constraints, which could be exploited by
future versions of this software.
Symbolic numerical constants are provided for compatibility only,
see section Monash Examples.
clp(q) ?- { 2*X+Y =< 16, X+2*Y =< 11,
X+3*Y =< 15, Z = 30*X+50*Y
}, sup(Z, Sup).
Sup = 310,
{Z=30*X+50*Y},
{X+1/2*Y=<8},
{X+3*Y=<15},
{X+2*Y=<11}
minimize(Expr) :- inf(Expr, Expr).
clp(q) ?- { 2*X+Y =< 16, X+2*Y =< 11,
X+3*Y =< 15, Z = 30*X+50*Y
}, maximize(Z).
X = 7,
Y = 2,
Z = 310
clp(r) ?- {2*A+3*B=C/2}, C=10.0, A=B.
A = 1.0,
B = 1.0,
C = 10.0
Is equivalent modulo rounding errors to
clp(r) ?- {2*A+3*B=C/2, C=10, A=B}.
A = 1.0,
B = 0.9999999999999999,
C = 10.0
The shortcut bypassing the use of {}/1
is allowed and makes sense because the interpretation of
this equality in Prolog and clp(R) coincides.
In general, equations involving interpreted functors, +/2 in this case,
must be fed to the solver explicitly:
clp(r) ?- X=3.0+1.0, X=4.0. noFurther, variables known by clp(R) may be bound directly to floats only. Likewise, variables known by clp(Q) may be bound directly to rational numbers only, see section Rationals. Failing to do so is rewarded with an exception:
clp(q) ?- {2*A+3*B=C/2}, C=10.0, A=B.
{ERROR: not_normalized(10.0)}
This is because 10.0 is not a rational constant. To make clp(Q) happy
you have to say:
clp(q) ?- {2*A+3*B=C/2}, C=rat(10,1), A=B.
A = 1,
B = 1,
C = 10
If you use {}/1, you don't have to worry about such details.
Alternatively, you may use the automatic expansion facility, check section Syntactic Sugar.
clp(r) ?- {A-B+C=10, C=5+5}.
B = A,
C = 10.0
The linear constraints imply A=B and the solver consequently
exports this binding to the Prolog world, which is manifest in the fact
that the test A==B will succeed.
More about answer presentation in section Projection and Redundancy Elimination.
clp(r) ?- {sin(X) = cos(X)}.
nonlin:{sin(X)-cos(X)=0.0}
There are indeed infinitely many solutions to this constraint
(X = 0.785398 + n*Pi), but clp(Q,R) has no direct means to find
and represent them.
The systems goes through some lengths to recognize linear expressions as such. The method is based on a normal form for multivariate polynomials. In addition, some simple isolation axioms, that can be used in equality constraints, have been added. The current major limitation of the method is that full polynomial division has not been implemented. Examples:
This is an example where the isolation axioms are sufficient to determine the value of X.
clp(r) ?- {sin(cos(X)) = 1/2}.
X = 1.0197267436954502
If we change the equation into an inequation, clp(Q,R) gives up:
clp(r) ?- {sin(cos(X)) < 1/2}.
nonlin:{sin(cos(X))-0.5<0.0}
The following is easy again:
clp(r) ?- {sin(X+2+2)/sin(4+X) = Y}.
Y = 1.0
And so is this:
clp(r) ?- {(X+Y)*(Y+X)/X = Y*Y/X+99}.
{Y=49.5-0.5*X}
An ancient symbol manipulation benchmark consists in rising the expression
X+Y+Z+1 to the 15th power:
clp(q) ?- {exp(X+Y+Z+1,15)=0}.
nonlin:{Z^15+Z^14*15+Z^13*105+Z^12*455+Z^11*1365+Z^10*3003+...
... polynomial continues for a few pages ...
=0}
Computing its roots is another story.
clp(q) ?- {exp(X+Y+1,2) = 3*X*X+Y*Y}.
nonlin:{Y*2-X^2*2+Y*X*2+X*2+1=0}
Equating X and Y collapses the expression completely
and even determines the values of the two variables:
clp(q) ?- {exp(X+Y+1,2) = 3*X*X+Y*Y}, X=Y.
X = -1/4,
Y = -1/4
clp(r) ?- { 12=pow(2,X) }.
X = 3.5849625007211565
clp(r) ?- { 12=pow(X,3.585) }.
X = 1.9999854993443926
clp(r) ?- { X=pow(2,3.585) }.
X = 12.000311914286545
clp(r) ?- { 1/2 = sin(X) }.
X = 0.5235987755982989
What is to be kept in mind however is the fact that it may take quite big rationals to accommodate the required precision. High levels of precision are for example required if your linear program is ill-conditioned, i.e., in a full rank system the determinant of the coefficient matrix is close to zero. Another situation that may call for elevated levels of precision is when a linear optimization problem requires exceedingly many pivot steps before the optimum is reached.
If your application approximates irrational numbers, you may be out of space particularly soon. The following program implements N steps of Newton's approximation for the square root function at point 2.
%
% from file: library('clpqr/examples/root')
%
root(N, R) :-
root(N, 1, R).
root(0, S, R) :- !, S=R.
root(N, S, R) :-
N1 is N-1,
{ S1 = S/2 + 1/S },
root(N1, S1, R).
It is known that this approximation converges quadratically, which
means that the number of correct digits in the decimal expansion
roughly doubles with each iteration. Therefore the numerator and
denominator of the rational approximation have to grow likewise:
clp(q) ?- use_module(library('clpqr/examples/root')).
clp(q) ?- root(3,R),print_decimal(R,70).
1.4142156862 7450980392 1568627450 9803921568 6274509803 9215686274
5098039215
R = 577/408
clp(q) ?- root(4,R),print_decimal(R,70).
1.4142135623 7468991062 6295578890 1349101165 5962211574 4044584905
0192000543
R = 665857/470832
clp(q) ?- root(5,R),print_decimal(R,70).
1.4142135623 7309504880 1689623502 5302436149 8192577619 7428498289
4986231958
R = 886731088897/627013566048
clp(q) ?- root(6,R),print_decimal(R,70).
1.4142135623 7309504880 1688724209 6980785696 7187537723 4001561013
1331132652
R = 1572584048032918633353217/1111984844349868137938112
clp(q) ?- root(7,R),print_decimal(R,70).
1.4142135623 7309504880 1688724209 6980785696 7187537694 8073176679
7379907324
R = 4946041176255201878775086487573351061418968498177 /
3497379255757941172020851852070562919437964212608
Iterating for 8 steps produces no further change in the first 70 decimal digits
of sqrt(2). After 15 steps the approximating rational number has a
numerator and a denominator with 12543 digits each, and the next step runs
out of memory.
Another irrational number that is easily computed is e.
The following program implements an alternating series
for 1/e, where the absolute value of last term is an
upper bound on the error.
%
% from file: library('clpqr/examples/root')
%
e(N, E) :-
{ Err =:= exp(10,-(N+2)), Half =:= 1/2 },
inv_e_series(Half, Half, 3, Err, Inv_E),
{ E =:= 1/Inv_E }.
inv_e_series(Term, S0, _, Err, Sum) :-
{ abs(Term) =< Err }, !,
S0 = Sum.
inv_e_series(Term, S0, N, Err, Sum) :-
N1 is N+1,
{ Term1 =:= -Term/N, S1 =:= Term1+S0 },
inv_e_series(Term1, S1, N1, Err, Sum).
The computation of the rational number E that approximates e up
to at least
1000 digits in its decimal expansion requires the evaluation of 450 terms of
the series, i.e. 450 calls of inv_e_series/5.
clp(q) ?- e(1000,E).
E = 7149056228932760213666809592072842334290744221392610955845565494
3708750229467761730471738895197792271346693089326102132000338192
0131874187833985420922688804220167840319199699494193852403223700
5853832741544191628747052136402176941963825543565900589161585723
4023097417605004829991929283045372355639145644588174733401360176
9953973706537274133283614740902771561159913069917833820285608440
3104966899999651928637634656418969027076699082888742481392304807
9484725489080844360397606199771786024695620205344042765860581379
3538290451208322129898069978107971226873160872046731879753034549
3130492167474809196348846916421782850086985668680640425192038155
4902863298351349469211627292865440876581064873866786120098602898
8799130098877372097360065934827751120659213470528793143805903554
7928682131082164366007016698761961066948371407368962539467994627
1374858249110795976398595034606994740186040425117101588480000000
0000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000
/
2629990810403002651095959155503002285441272170673105334466808931
6863103901346024240326549035084528682487048064823380723787110941
6809235187356318780972302796570251102928552003708556939314795678
1978390674393498540663747334079841518303636625888963910391440709
0887345797303470959207883316838346973393937778363411195624313553
8835644822353659840936818391050630360633734935381528275392050975
7271468992840907541350345459011192466892177866882264242860412188
0652112744642450404625763019639086944558899249788084559753723892
1643188991444945360726899532023542969572584363761073528841147012
2634218045463494055807073778490814692996517359952229262198396182
1838930043528583109973872348193806830382584040536394640895148751
0766256738740729894909630785260101721285704616818889741995949666
6303289703199393801976334974240815397920213059799071915067856758
6716458821062645562512745336709063396510021681900076680696945309
3660590933279867736747926648678738515702777431353845466199680991
73361873421152165477774911660108200059
The decimal expansion itself looks like this:
clp(q) ?- e(1000, E), print_decimal(E, 1000). 2. 7182818284 5904523536 0287471352 6624977572 4709369995 9574966967 6277240766 3035354759 4571382178 5251664274 2746639193 2003059921 8174135966 2904357290 0334295260 5956307381 3232862794 3490763233 8298807531 9525101901 1573834187 9307021540 8914993488 4167509244 7614606680 8226480016 8477411853 7423454424 3710753907 7744992069 5517027618 3860626133 1384583000 7520449338 2656029760 6737113200 7093287091 2744374704 7230696977 2093101416 9283681902 5515108657 4637721112 5238978442 5056953696 7707854499 6996794686 4454905987 9316368892 3009879312 7736178215 4249992295 7635148220 8269895193 6680331825 2886939849 6465105820 9392398294 8879332036 2509443117 3012381970 6841614039 7019837679 3206832823 7646480429 5311802328 7825098194 5581530175 6717361332 0698112509 9618188159 3041690351 5988885193 4580727386 6738589422 8792284998 9208680582 5749279610 4841984443 6346324496 8487560233 6248270419 7862320900 2160990235 3043699418 4914631409 3431738143 6405462531 5209618369 0888707016 7683964243 7814059271 4563549061 3031072085 1038375051 0115747704 1718986106 8739696552 1267154688 9570350354
mortgage relation:
%
% from file: library('clpqr/examples/mg')
%
mg(P,T,I,B,MP):-
{
T = 1,
B + MP = P * (1 + I)
}.
mg(P,T,I,B,MP):-
{
T > 1,
P1 = P * (1 + I) - MP,
T1 = T - 1
},
mg(P1, T1, I, B, MP).
A sample query yields:
clp(r) ?- use_module(library('clpqr/examples/mg')).
clp(r) ?- mg(P,12,0.01,B,Mp).
{B=1.1268250301319698*P-12.682503013196973*Mp}
Without projection of the answer constraints onto the query variables we
would observe the following interaction:
clp(r) ?- mg(P,12,0.01,B,Mp).
{B=12.682503013196973*_A-11.682503013196971*P},
{Mp= -(_A)+1.01*P},
{_B=2.01*_A-1.01*P},
{_C=3.0301*_A-2.0301*P},
{_D=4.060401000000001*_A-3.0604009999999997*P},
{_E=5.101005010000001*_A-4.10100501*P},
{_F=6.152015060100001*_A-5.152015060099999*P},
{_G=7.213535210701001*_A-6.213535210700999*P},
{_H=8.285670562808011*_A-7.285670562808009*P},
{_I=9.368527268436091*_A-8.36852726843609*P},
{_J=10.462212541120453*_A-9.46221254112045*P},
{_K=11.566834666531657*_A-10.566834666531655*P}
The variables _A @dots{} _K are not part of the query, they
originate from the mortgage program proper. Although the latter answer
is equivalent to the former in terms of linear algebra, most users would
prefer the former.
ordering(+Spec) gives
you some control over the variable ordering. Suppose that instead of
B, you want Mp to be the defined variable:
clp(r) ?- mg(P,12,0.01,B,Mp).
{B=1.1268250301319698*P-12.682503013196973*Mp}
This is achieved with:
clp(r) ?- mg(P,12,0.01,B,Mp), ordering([Mp]).
{Mp= -0.0788487886783417*B+0.08884878867834171*P}
One could go one step further and require P to appear before
(to the left of) B in a addition:
clp(r) ?- mg(P,12,0.01,B,Mp), ordering([Mp,P]).
{Mp=0.08884878867834171*P-0.0788487886783417*B}
Spec in ordering(+Spec) is either a list of variables with
the intended ordering, or of the form A<B.
The latter form means that A goes to the left of B.
In fact, ordering([A,B,C,D]) is shorthand for:
ordering(A < B), ordering(A < C), ordering(A < D), ordering(B < C), ordering(B < D), ordering(C < D)
The ordering specification only affects the final presentation of the
constraints. For all other operations of clp(Q,R), the ordering is immaterial.
Note that ordering/1 acts like a constraint: you can put it anywhere
in the computation, and you can submit multiple specifications.
clp(r) ?- ordering(B < Mp), mg(P,12,0.01,B,Mp).
{B= -12.682503013196973*Mp+1.1268250301319698*P}
yes
clp(r) ?- ordering(B < Mp), mg(P,12,0.01,B,Mp), ordering(P < Mp).
{P=0.8874492252651537*B+11.255077473484631*Mp}
call_residue/2 provides this functionality:
clp(r) ?- call_residue({2*A+B+C=10,C-D=E,A<10}, Constraints).
Constraints = [
[A]-{A<10.0},
[B]-{B=10.0-2.0*A-C},
[D]-{D=C-E}
]
n-1 variables via implicit projection.
In order to make answers as concise as possible, redundant constraints are removed by the system as well. In the following set of inequalities, half of them are redundant.
%
% from file: library('clpqr/examples/elimination')
%
example(2, [X0,X1,X2,X3,X4]) :-
{
+87*X0 +52*X1 +27*X2 -54*X3 +56*X4 =< -93,
+33*X0 -10*X1 +61*X2 -28*X3 -29*X4 =< 63,
-68*X0 +8*X1 +35*X2 +68*X3 +35*X4 =< -85,
+90*X0 +60*X1 -76*X2 -53*X3 +24*X4 =< -68,
-95*X0 -10*X1 +64*X2 +76*X3 -24*X4 =< 33,
+43*X0 -22*X1 +67*X2 -68*X3 -92*X4 =< -97,
+39*X0 +7*X1 +62*X2 +54*X3 -26*X4 =< -27,
+48*X0 -13*X1 +7*X2 -61*X3 -59*X4 =< -2,
+49*X0 -23*X1 -31*X2 -76*X3 +27*X4 =< 3,
-50*X0 +58*X1 -1*X2 +57*X3 +20*X4 =< 6,
-13*X0 -63*X1 +81*X2 -3*X3 +70*X4 =< 64,
+20*X0 +67*X1 -23*X2 -41*X3 -66*X4 =< 52,
-81*X0 -44*X1 +19*X2 -22*X3 -73*X4 =< -17,
-43*X0 -9*X1 +14*X2 +27*X3 +40*X4 =< 39,
+16*X0 +83*X1 +89*X2 +25*X3 +55*X4 =< 36,
+2*X0 +40*X1 +65*X2 +59*X3 -32*X4 =< 13,
-65*X0 -11*X1 +10*X2 -13*X3 +91*X4 =< 49,
+93*X0 -73*X1 +91*X2 -1*X3 +23*X4 =< -87
}.
Consequently, the answer consists of the system of nine non-redundant
inequalities only:
clp(q) ?- use_module(library('clpqr/examples/elimination')).
clp(q) ?- example(2, [X0,X1,X2,X3,X4]).
{X0-2/17*X1-35/68*X2-X3-35/68*X4>=5/4},
{X0-73/93*X1+91/93*X2-1/93*X3+23/93*X4=<-29/31},
{X0-29/25*X1+1/50*X2-57/50*X3-2/5*X4>=-3/25},
{X0+7/39*X1+62/39*X2+18/13*X3-2/3*X4=<-9/13},
{X0+2/19*X1-64/95*X2-4/5*X3+24/95*X4>=-33/95},
{X0+2/3*X1-38/45*X2-53/90*X3+4/15*X4=<-34/45},
{X0-23/49*X1-31/49*X2-76/49*X3+27/49*X4=<3/49},
{X0+44/81*X1-19/81*X2+22/81*X3+73/81*X4>=17/81},
{X0+9/43*X1-14/43*X2-27/43*X3-40/43*X4>=-39/43}
The projection (the shadow) of this polyhedral set into the X0,X1
space can be computed via the implicit elimination of non-query variables:
clp(q) ?- example(2, [X0,X1|_]).
{X0+2619277/17854273*X1>=-851123/17854273},
{X0+6429953/16575801*X1=<-12749681/16575801},
{X0+19130/1213083*X1>=795400/404361},
{X0-1251619/3956679*X1>=21101146/3956679},
{X0+601502/4257189*X1>=220850/473021}
Projection is quite a powerful concept that leads to surprisingly terse executable specifications of nontrivial problems like the computation of the convex hull from a set of points in an n-dimensional space: Given the program
%
% from file: library('clpqr/examples/elimination')
%
conv_hull(Points, Xs) :-
lin_comb(Points, Lambdas, Zero, Xs),
zero(Zero),
polytope(Lambdas).
polytope(Xs) :-
positive_sum(Xs, 1).
positive_sum([], Z) :- {Z=0}.
positive_sum([X|Xs], SumX) :-
{ X >= 0, SumX = X+Sum },
positive_sum(Xs, Sum).
zero([]).
zero([Z|Zs]) :- {Z=0}, zero(Zs).
lin_comb([], [], S1, S1).
lin_comb([Ps|Rest], [K|Ks], S1, S3) :-
lin_comb_r(Ps, K, S1, S2),
lin_comb(Rest, Ks, S2, S3).
lin_comb_r([], _, [], []).
lin_comb_r([P|Ps], K, [S|Ss], [Kps|Ss1]) :-
{ Kps = K*P+S },
lin_comb_r(Ps, K, Ss, Ss1).
we can post the following query:
clp(q) ?- conv_hull([ [1,1], [2,0], [3,0], [1,2], [2,2] ], [X,Y]).
{Y=<2},
{X+1/2*Y=<3},
{X>=1},
{Y>=0},
{X+Y>=2}
This answer is easily verified graphically:
|
2 - * *
|
|
1 - *
|
|
0 -----|----*----*----
1 2 3
The convex hull program directly corresponds to the mathematical
definition of the convex hull. What does the trick in operational terms
is the implicit elimination of the Lambdas from the program
formulation. Please note that this program does not limit the number of
points or the dimension of the space they are from. Please note further
that quantifier elimination is a computationally expensive operation and
therefore this program is only useful as a benchmark for the projector and
not so for the intended purpose.
Prolog-III program to clp(Q,R):
%
% from file: library('clpqr/examples/squares')
%
filled_rectangle(A, C) :-
{ A >= 1 },
distinct_squares(C),
filled_zone([-1,A,1], _, C, []).
distinct_squares([]).
distinct_squares([B|C]) :-
{ B > 0 },
outof(C, B),
distinct_squares(C).
outof([], _).
outof([B1|C], B) :-
{ B =\= B1 }, % *** note disequation ***
outof(C, B).
filled_zone([V|L], [W|L], C0, C0) :-
{ V=W,V >= 0 }.
filled_zone([V|L], L3, [B|C], C2) :-
{ V < 0 },
placed_square(B, L, L1),
filled_zone(L1, L2, C, C1),
{ Vb=V+B },
filled_zone([Vb,B|L2], L3, C1, C2).
placed_square(B, [H,H0,H1|L], L1) :-
{ B > H, H0=0, H2=H+H1 },
placed_square(B, [H2|L], L1).
placed_square(B, [B,V|L], [X|L]) :-
{ X=V-B }.
placed_square(B, [H|L], [X,Y|L]) :-
{ B < H, X= -B, Y=H-B }.
There are no tilings with less than nine squares except the trivial one
where the rectangle equals the only square. There are eight solutions
for nine squares. Six further solutions are rotations of the first two.
clp(q) ?- use_module(library('clpqr/examples/squares')).
clp(q) ?- filled_rectangle(A, Squares).
A = 1,
Squares = [1] ? ;
A = 33/32,
Squares = [15/32,9/16,1/4,7/32,1/8,7/16,1/32,5/16,9/32] ? ;
A = 69/61,
Squares = [33/61,36/61,28/61,5/61,2/61,9/61,25/61,7/61,16/61]
Depending on your hardware, the above query may take a few minutes.
Supplying the knowledge about the minimal number of squares
beforehand cuts the computation time by a factor of roughly four:
clp(q) ?- length(Squares, 9), filled_rectangle(A, Squares). A = 33/32, Squares = [15/32,9/16,1/4,7/32,1/8,7/16,1/32,5/16,9/32] ? ; A = 69/61, Squares = [33/61,36/61,28/61,5/61,2/61,9/61,25/61,7/61,16/61]
quote/1 (just as in LISP) and some means to put syntactical terms
back to their interpreted life: {}/1.
In a quote-eval language, meta-programming is (pragmatically) simpler because everything is implicitly quoted until explicitly evaluated. On the other hand, now object programming suffers from the dual inconvenience.
We chose to make our version of clp(Q,R) of the quote-eval type because this matches the intended use of the already existing boolean solver of SICStus. In order to keep the users of the eval-quote variant happy, we provide a source transformation package. It is activated via:
| ?- use_module(library('clpqr/expand')).
Loading the package puts you in a mode where the arithmetic functors
like +/2, */2 and all numbers (functors of arity 0) are
interpreted semantically.
clp(r) ?- 2+2=X. X = 4.0The package works by purifying programs and queries in the sense that all references to interpreted terms are made explicit. The above query is expanded prior to evaluation into:
linear:{2.0+2.0=X}
The same mechanism applies when interpreted terms are nested deeper:
some_predicate(10, f(A+B/2), 2*cos(A))Expands into:
linear:{Xc=2.0*cos(A)},
linear:{Xb=A+B/2},
linear:{Xa=10.0},
some_predicate(Xa, f(Xb), Xc)
This process also applies when files are consulted or compiled. In fact,
this is the only situation where expansion can be applied with relative
safety. To see this, consider what happens when the toplevel evaluates
the expansion, namely some calls to the clp(Q,R) solver, followed by the
call of the purified query. As we learned in section Feedback and Bindings, the solver may bind
variables, which produces a goal with interpreted functors in it (numbers),
which leads to another stage of expansion, and so on.
We recommend that you only turn on expansion temporarily while
consulting or compiling files needing expansion with expand/0
and noexpand/0.
In order to execute the examples, a small compatibility package has to be loaded first:
clp(r) ?- use_module(library('clpqr/monash')).
Then, assuming you are using clp(R):
clp(r) ?- expand, [library('clpqr/examples/monash/rkf45')],
noexpand.
clp(r) ?- go.
Point 0.00000 : 0.75000 0.00000
Point 0.50000 : 0.61969 0.47793
Point 1.00000 : 0.29417 0.81233
Point 1.50000 : -0.10556 0.95809
Point 2.00000 : -0.49076 0.93977
Point 2.50000 : -0.81440 0.79929
Point 3.00000 : -1.05440 0.57522
Iteration finished
------------------
439 derivative evaluations
rkf45 complete nicely in clp(Q). With rkf45,
clp(Q) runs out of memory. This is an instance of the problem
discussed in section Numerical Precision and Rationals.
The Monash University clp(R) interpreter features a dump/n
predicate. It is used to print the target variables
according to the given ordering.
Within this version of clp(Q,R), the corresponding functionality
is provided via ordering/1. The difference is that ordering/1
does only specify the ordering of the variables and no printing
is performed. We think Prolog has enough predicates to perform output already.
You can still run the examples referring to dump/n from
the Prolog toplevel:
clp(r) ?- expand, [library('clpqr/examples/monash/mortgage')], noexpand.
% go2
%
clp(r) ?- mg(P,120,0.01,0,MP), dump([P,MP]).
{P=69.7005220313972*MP}
% go3
%
clp(r) ?- mg(P,120,0.01,B,MP), dump([P,B,MP]).
{P=0.30299477968602706*B+69.7005220313972*MP}
% go4
%
clp(r) ?- mg(999, 3, Int, 0, 400), dump.
nonlin:{_B-_B*Int+_A+400.0=0.0},
nonlin:{_A-_A*Int+400.0=0.0},
{_B=599.0+999.0*Int}
NAME: flugpl
ROWS: 18
COLUMNS: 18
INTEGER: 11
NONZERO: 46
BEST SOLN: 1201500 (opt)
LP SOLN: 1167185.73
SOURCE: Harvey M. Wagner
John W. Gregory (Cray Research)
E. Andrew Boyd (Rice University)
APPLICATION: airline model
COMMENTS: no integer variables are binary
%
% from file: library('clpqr/examples/mip')
%
example(flugpl, Obj, Vs, Ints, []) :-
Vs = [ Anm1,Anm2,Anm3,Anm4,Anm5,Anm6,
Stm1,Stm2,Stm3,Stm4,Stm5,Stm6,
UE1,UE2,UE3,UE4,UE5,UE6],
Ints = [Stm6, Stm5, Stm4, Stm3, Stm2,
Anm6, Anm5, Anm4, Anm3, Anm2, Anm1],
Obj = 2700*Stm1 + 1500*Anm1 + 30*UE1
+ 2700*Stm2 + 1500*Anm2 + 30*UE2
+ 2700*Stm3 + 1500*Anm3 + 30*UE3
+ 2700*Stm4 + 1500*Anm4 + 30*UE4
+ 2700*Stm5 + 1500*Anm5 + 30*UE5
+ 2700*Stm6 + 1500*Anm6 + 30*UE6,
allpos(Vs),
{ Stm1 = 60, 0.9*Stm1 +1*Anm1 -1*Stm2 = 0,
0.9*Stm2 +1*Anm2 -1*Stm3 = 0, 0.9*Stm3 +1*Anm3 -1*Stm4 = 0,
0.9*Stm4 +1*Anm4 -1*Stm5 = 0, 0.9*Stm5 +1*Anm5 -1*Stm6 = 0,
150*Stm1 -100*Anm1 +1*UE1 >= 8000,
150*Stm2 -100*Anm2 +1*UE2 >= 9000,
150*Stm3 -100*Anm3 +1*UE3 >= 8000,
150*Stm4 -100*Anm4 +1*UE4 >= 10000,
150*Stm5 -100*Anm5 +1*UE5 >= 9000,
150*Stm6 -100*Anm6 +1*UE6 >= 12000,
-20*Stm1 +1*UE1 =< 0, -20*Stm2 +1*UE2 =< 0, -20*Stm3 +1*UE3 =< 0,
-20*Stm4 +1*UE4 =< 0, -20*Stm5 +1*UE5 =< 0, -20*Stm6 +1*UE6 =< 0,
Anm1 =< 18, 57 =< Stm2, Stm2 =< 75, Anm2 =< 18,
57 =< Stm3, Stm3 =< 75, Anm3 =< 18, 57 =< Stm4,
Stm4 =< 75, Anm4 =< 18, 57 =< Stm5, Stm5 =< 75,
Anm5 =< 18, 57 =< Stm6, Stm6 =< 75, Anm6 =< 18
}.
allpos([]).
allpos([X|Xs]) :- {X >= 0}, allpos(Xs).
We can first check whether the relaxed problem has indeed the quoted infimum:
clp(r) ?- example(flugpl, Obj, _, _, _), inf(Obj, Inf). Inf = 1167185.7255923203
Computing the infimum under the additional constraints that Stm6,
Stm5, Stm4, Stm3, Stm2, Anm6,
Anm5, Anm4, Anm3, Anm2, Anm1 assume
integer values at the infimum is computationally harder, but the query
does not change much:
clp(r) ?- example(flugpl, Obj, _, Ints, _), bb_inf(Ints, Obj, Inf). Inf = 1201500.0000000005
rat(Num,Den).
Den is always positive, i.e. the sign of the rational number is the
sign of Num. Further, Num and Den are relative prime.
Note that integer N looks like rat(N,1) in this representation.
You can control printing of terms with portray/1.
call_residue/2 for the expansion of {}/1
(see section Term and Goal Expansion, hook predicate user:goal_expansion/3).
clp(r) ?- {A < 10}, assert(p(A)).
{A<10.0}
yes
clp(r) ?- p(X).
{X<10.0}
Please send bug reports to <christian@ai.univie.ac.at>.
Go to the previous, next section.