Did you know ... | Search Documentation: |
![]() | Pack clpBNR -- prolog/clpBNR_toolkit.pl |
CLP(BNR) (library(clpBNR)
) is a CLP over the domain of real numbers extended with ±∞. This module contains a number of useful utilities for specific problem domains like the optimization of linear systems, enforcing local optima conditions, and constructing centre form contractors to improve performance (e.g., Taylor extensions of constraints). For more detailed discussion, see A Guide to CLP(BNR) (HTML version included with this pack in directory docs/
).
Documentation for exported predicates follows. The "custom" types include:
clpBNR
attributesmall/2
and Goal midsplit/1
:
?- X::real(-1,1),iterate_until(10,small(X,0),mid_split(X)),format("X = ~w\n",X),fail;true. X = _6288{real(-1,-1r2)} X = _6288{real(-1r2,0)} X = _6288{real(0,1r2)} X = _6288{real(1r2,1)} true.
The specific intended use case is to provide an iterator for meta-contractors such as the centre-form contractor such as midsplit/1
(example above) or as constructed by taylor_contractor/2
as in:
?- X::real,taylor_contractor({X**4-4*X**3+4*X**2-4*X+3==0},T), iterate_until(50,small(X),(T,mid_split_one([X]))),format("X = ~w\n",X),fail;true. X = _150{real(0.999999999926943,1.00000000007306)} X = _150{real(2.999999999484828,3.0000000005152105)} true.
(Aside: For some problems, solving with Taylor contractors can be a faster and more precise alternative to clpBNR:solve/1
.)
mid_split
for details of interval splitting for this predicate.
mid_split(X) :- M is midpoint(X), ({X=<M} ; {M=<X}).
Note that mid_split
succeeds if X is a number, but doesn't do anything.
Use clpBNR:small
as a pre-test to avoid splitting intervals which are already small enough.
taylor_contractor
. In normal usage, a direct call to cf_contractor
does appear; instead use cf_contractor
or in a Goal
for iterate_until/3
.
cf_solve/2
using default precision.clpBNR_default_precision
); otherwise fails.
This is done by using iterate_until/3
limited to a count determined by the flag clpBNR_iteration_limit
. Examples:
?- X::real, taylor_contractor({X**4-4*X**3+4*X**2-4*X+3==0},T), cf_solve(T). T = cf_contractor([X], [_A]), X:: 1.000000000..., _A::real(-1.0Inf, 1.0Inf) ; T = cf_contractor([X], [_A]), X:: 3.00000000..., _A::real(-1.0Inf, 1.0Inf) ; false. ?- taylor_contractor({2*X1+5*X1**3+1==X2*(1+X2), 2*X2+5*X2**3+1==X1*(1+X1)},T), cf_solve(T). T = cf_contractor([X2, X1], [_A, _B]), X1:: -0.42730462..., X2:: -0.42730462..., _B::real(-1.0Inf, 1.0Inf), _A::real(-1.0Inf, 1.0Inf) ; false.
==
or =:=
) constraints Constraints; otherwise fails. Example:
?- taylor_contractor({X**4-4*X**3+4*X**2-4*X+3==0},T). T = cf_contractor([X], [_A]), X::real(-1.509169756145379, 4.18727500493995), _A::real(-1.0Inf, 1.0Inf).
Use the contractor with cf_solve
to search for solutions, as in:
?- X::real,taylor_contractor({X**4-4*X**3+4*X**2-4*X+3==0},T), cf_solve(T). T = cf_contractor([X], [_A]), X:: 1.000000000..., _A::real(-1.0Inf, 1.0Inf) ; T = cf_contractor([X], [_A]), X:: 3.00000000..., _A::real(-1.0Inf, 1.0Inf) ; false.
Multiple equality constraints are supported, as in this example of the Broyden banded problem (N=2):
?- taylor_contractor({2*X1+5*X1**3+1==X2*(1+X2), 2*X2+5*X2**3+1==X1*(1+X1)},T), cf_solve(T). T = cf_contractor([X2, X1], [_A, _B]), X1:: -0.42730462..., X2:: -0.42730462..., _B::real(-1.0Inf, 1.0Inf), _A::real(-1.0Inf, 1.0Inf) ; false.
Centre form contractors can converge faster than the general purpose builtin fixed point iteration provided by solve/1
.
==
or =:=
) constraint in Constraints; otherwise fails.
integrate/4
with default precision.The number of integration steps (= 2**P) is determined by the precision parameter P (default is value of environment flag clpBNR_default_precision). Example of use with increasing precision values:
?- X::real(0.0,1.0), F=X**2, between(2,10,P),integrate(F,X,RV,P), range(RV,R), format('~w:~w\n',[P,R]), fail. 2:[0.328125,0.359375] 3:[0.33203125,0.33984375] 4:[0.3330078125,0.3349609375] 5:[0.333251953125,0.333740234375] 6:[0.33331298828125,0.33343505859375] 7:[0.3333282470703125,0.3333587646484375] 8:[0.3333320617675781,0.3333396911621094] 9:[0.33333301544189453,0.33333492279052734] 10:[0.33333325386047363,0.33333373069763184] false.
boundary_values/4
with default precision and discarding steps list.boundary_values/4
discarding steps list.dV(Y, Fxy, Yi, Yf)
. The initial and final values of the independent variable for the purposes of the boundary value problem are specified by the lower and upper values of the domain of X. The arguments of for dvar/4
are:
The optional third argument P defines a precision value, a positive integer (default = environment flag clpBNR_default_precision
), which controls the the numerical integration; larger P means smaller step size.
The arity 4 version has an additional (final) argument which is unified with a list of the step values generated by the integration; each value is a tuple of the form (X,Ys)
.
This predicate fails if any of the arguments are invalid (generates an error message if clpBNR
debug topic is enabled) or if a solution to the boundary value problem cannot be found. Examples for X in the range 0..1 and derivative of Y = -2*X*Y
:
?- X::real(0,1), boundary_values(X,[dV(Y, -2*X*Y,1,Yf)]). X::real(0, 1), Yf:: 0.368... . ?- X::real(0,1),boundary_values(X,[dV(Y, -2*X*Y,1,Yf)],9). X::real(0, 1), Yf:: 0.36788... . ?- X::real(0,1), boundary_values(X,[dV(Y, -2*X*Y,Yi,1/e)]). X::real(0, 1), Yi:: 1.00... . ?- debug(clpBNR). true. ?- X=42, boundary_values(X,[dV(Y, -2*X*Y,Yi,1/e)]). % Invalid argument(s): boundary_values(42,[dV(_10836,-2*42*_10836,_10850,1/e)],6) false.
As with any application requiring numerical integration, care must be taken to avoid instability problems (more discussion in A Guide to CLP(BNR).
X*C
(or C*X
) are permitted since the actual computation is done using library(simplex)
. Narrowing of minimizers (variables in ObjF) is limited to that constrained by the Min result to accomodate multiple sets of minimizers. (See lin_minimize/3
to use minimizers used to derive Min.) A solution generator, e.g., clpBNR:solve/1
can be used to search for alternative sets of minimizers. "Universal Mines" example from the User Guide:
?- [M_Idays,M_IIdays,M_IIIdays]::integer(0,7), lin_minimum(20*M_Idays+22*M_IIdays+18*M_IIIdays, {4*M_Idays+6*M_IIdays+M_IIIdays>=54,4*M_Idays+4*M_IIdays+6*M_IIIdays>=65}, Min). Min = 284, M_Idays::integer(2, 7), M_IIdays::integer(4, 7), M_IIIdays::integer(2, 7). ?- [M_Idays,M_IIdays,M_IIIdays]::integer(0,7), lin_minimum(20*M_Idays+22*M_IIdays+18*M_IIIdays, {4*M_Idays+6*M_IIdays+M_IIIdays>=54,4*M_Idays+4*M_IIdays+6*M_IIIdays>=65}, Min), solve([M_Idays,M_IIdays,M_IIIdays]). M_Idays = 2, M_IIdays = 7, M_IIIdays = 5, Min = 284 ; false.
For linear systems, lin_minimum/3
, lin_maximum/3
can be significantly faster than using the more general purpose clpBNR:global_minimum/3
, clpBNR:global_maximum/3
lin_minimum/3
for finding global maxima.
lin_minimum/3
except variables in ObjF will be narrowed to the values used in calculating the final value of Min. Any other sets of minimizers corresponding to Min are removed from the solution space. "Universal Mines" example from the User Guide:
?- [M_Idays,M_IIdays,M_IIIdays]::integer(0,7), lin_minimize(20*M_Idays+22*M_IIdays+18*M_IIIdays, {4*M_Idays+6*M_IIdays+M_IIIdays>=54,4*M_Idays+4*M_IIdays+6*M_IIIdays>=65}, Min). M_Idays = 2, M_IIdays = 7, M_IIIdays = 5, Min = 284.
lin_maximum/3
except variables in ObjF will be narrowed to the values used in calculating the final value of Max. Any other sets of minimizers corresponding to Min are removed from the solution space.
local_minima
should be executed prior to a call to clpBNR:global_minimum
using the same objective function, e.g.,
?- X::real(0,10), OF=X**3-6*X**2+9*X+6, local_minima(OF), global_minimum(OF,Z). OF = X**3-6*X**2+9*X+6, X:: 3.00000000000000..., Z:: 6.000000000000... .
Using any local optima predicate can significantly improve performance compared to searching for global optima (clpBNR:global_
*) without local constraints.
local_maxima
should be executed prior to a call to clpBNR:global_maximum
using the same objective function, e.g.,
?- X::real(0,10), OF=X**3-6*X**2+9*X+6, local_maxima(OF), global_maximum(OF,Z). OF = X**3-6*X**2+9*X+6, X:: 1.000000000000000..., Z:: 10.0000000000000... .
local_minima
should be executed prior to a call to clpBNR:global_minimum
using the same objective function, e.g.,
?- [X1,X2]::real, OF=X1**4*exp(-0.01*(X1*X2)**2), local_minima(OF,{2*X1**2+X2**2==10}), global_minimum(OF,Z), solve([X1,X2]). OF = X1**4*exp(-0.01*(X1*X2)**2), X1::real(-1.703183936003284e-108, 1.703183936003284e-108), X2:: -3.16227766016838..., Z:: 0.0000000000000000... ; OF = X1**4*exp(-0.01*(X1*X2)**2), X1::real(-1.703183936003284e-108, 1.703183936003284e-108), X2:: 3.16227766016838..., Z:: 0.0000000000000000... .
local_maxima
should be executed prior to a call to clpBNR:global_maximum
using the same objective function, e.g.,
?- [X1,X2]::real,OF=X1**4*exp(-0.01*(X1*X2)**2), local_maxima(OF,{2*X1**2+X2**2==10}), global_maximum(OF,Z),solve([X1,X2]). OF = X1**4*exp(-0.01*(X1*X2)**2), X1:: -2.23606797749979..., X2:: 0.0000000000000000..., Z:: 25.0000000000000... ; OF = X1**4*exp(-0.01*(X1*X2)**2), X1:: 2.23606797749979..., X2:: 0.0000000000000000..., Z:: 25.0000000000000... .