Subsections

• A note on Prolog IV and

Non-Linear Solver: Intervals

The linear equations solver we have been seeing has the attractive of being complete (i.e., it always finds a correct solution if it exists, and says that no solution exists only when this is the case). But, on the other hand, it can solve only linear equations. Prolog IV implements a second numerical constraint system which is based on intervals: variables take values in intervals (and combinations thereof) of real numbers, which in fact associates a (potentially) infinite number of points to each variable. Intervals have a special syntax in Prolog IV, and the usual mathematical combinations of open / closed interval are available. Table 3.1 shows the four different types of intervals and their syntax.

 

Table 3.1: Intervals and their representation in Prolog IV

Interval	From	To	Prolog IV
[X, Y]	X (included)	Y (included)	cc(X, Y)
(X, Y]	X (excluded)	Y (included)	oc(X, Y)
[X, Y)	X (included)	Y (excluded)	co(X, Y)
(X, Y)	X (excluded)	Y (excluded)	oo(X, Y)

 

Using intervals brings advantages in some cases. Non-linear equations can be approximately solved, and intervals can also be used to simulate easily finite domains (by forcing the interval to contain only integer values). On the other hand, it is not sure that a solution will be found for non-linear problems. For this reasons, it is convenient to know when the linear solver has to be used, and when the non-linear solver is the correct choice. Thus, it is necessary to be able to tell Prolog IV which solver we want to use in every particular case. This is done by using different keywords to express operations in the linear and non-linear solver; the two versions are shown in Table 3.2. The suffix lin is removed from the relational constraints, and dots are added in before and after the arithmetical operators. The equality constraint =/2 remains the same. But the ``compatible with'' operator, $\sim$, particular to Prolog IV, is to be used to bind variables to intervals:

?- X = A .+. B, A ~ cc(1, 3), B ~ cc(3, 7). 
   B ~ cc(3,7), A ~ cc(1,3), X ~ cc(4,10). 

?- X = A .-. B, A ~ cc(1, 3), B ~ cc(3, 7). 
   B ~ cc(3,7), A ~ cc(1,3), X ~ cc(-6,0).

In their basic version, operations on intervals just add, subtract, etc. the maxima and minima of the ranges of the variables, which are updated to make the operations true--always in the direction of narrowing the intervals. In more complex problems, the intervals are successively narrowed using an iterative procedure until a fixpoint is reached:

?- X = A .-. B, A ~ cc(1,3), ge(X,0), B ~ cc(3,7). 
   B = 3, A = 3, X = 0.

 

Table 3.2: Correspondence between keywords for the linear and non-linear solvers

Linear version	Non-linear (intervals) version
_ + _	_ .+. _
_ - _	_ .-. _
_ * _	_ .*. _
_ / _	_ ./. _
gtlin(_, _)	gt(_, _)
gelin(_, _)	ge(_, _)
ltlin(_, _)	lt(_, _)
lelin(_, _)	le(_, _)

 

A note on Prolog IV and

The use of in Prolog IV is a shorthand for writing more complex relations: an expression like A cc(1, 3) is a shortened form of cc(A, 1, 3) where cc/3 is a relation which states that A can take values in the interval [1, 3]. Similarly, the expression gt(A, 0), which stands for A > 0, can also be written A gt(0), and other constructions as for example .*. are abbreviated forms for relations: writing X = A .*. B is akin to writing times(X, A, B).