Package "clpBNR"

Title:	CLP over Reals using Interval Arithmetic - includes Rational, Integer and Boolean domains as subsets.
Rating:	Not rated. Create the first rating!
Latest version:	0.11.10
SHA1 sum:	0bf7d4ddfc5b58a22d8a4196f64efa17c4a27fa8
Author:	Rick Workman <ridgeworks@mac.com>
Home page:	https://github.com/ridgeworks/clpBNR
Download URL:	https://github.com/ridgeworks/clpBNR.git
Requires:	prolog:rationals
	prolog>=9.1.22

Reviews

No reviews. Create the first review!.

Details by download location

Version	SHA1	#Downloads	URL
0.8.1	3c3b4f5bc605a58d07a782c968150f52282beb59	2	https://ridgeworks.github.io/clpBNR_pl/Package/clpBNR-0.8.1.zip
0.8.2	3d390e89e035920da27676efa34f5e9e1cc8f3d9	8	https://ridgeworks.github.io/clpBNR_pl/Package/clpBNR-0.8.2.zip
0.9.0	6f73dc3f6bf2b51ee060f01d473ce4c859b26b88	10	https://ridgeworks.github.io/clpBNR_pl/Package/clpBNR-0.9.0.zip
0.9.1	e2073fef85d72018ea3102c9e0fcbd364e153c71	3	https://ridgeworks.github.io/clpBNR_pl/Package/clpBNR-0.9.1.zip
0.9.2	7c7900b2b3ff79c5b4c852c524b064a9b5e9b294	3	https://ridgeworks.github.io/clpBNR_pl/Package/clpBNR-0.9.2.zip
0.9.3	0cc6e4310624344c3331fcd839f4bde8cc01a0d0	5	https://ridgeworks.github.io/clpBNR_pl/Package/clpBNR-0.9.3.zip
0.9.4	90668870b53a0af8a02bb299404164abe9339d3d	15	https://ridgeworks.github.io/clpBNR_pl/Package/clpBNR-0.9.4.zip
0.9.5	e6a1d2f94d4a51e2432ae6dd4ec5f0325af7f567	6	https://github.com/ridgeworks/clpBNR.git
	f53d53b17e4f74b861d8e7f52bb9a4512875f60c	2	https://github.com/ridgeworks/clpBNR.git
0.9.6	4a9664dea65f63c18b724cde2e36c6f6bfd2c6a1	4	https://github.com/ridgeworks/clpBNR.git
0.9.7	6623460ab6b4361600036419f38552dc587b2313	4	https://github.com/ridgeworks/clpBNR.git
0.9.8	162da0e2c3ac9cbea17eb8370d4d59fc568d4012	5	https://github.com/ridgeworks/clpBNR.git
	fe2544e04bd175e57e2a9bea8800733874755122	3	https://github.com/ridgeworks/clpBNR.git
0.9.9	1976c9e2dd548aec4076c170a5a79ee537500f37	34	https://github.com/ridgeworks/clpBNR.git
0.9.10	f208ca94d1ffb75f29ac6be147940b73127b153a	5	https://github.com/ridgeworks/clpBNR.git
0.9.11	477a873bef498426e6f162d378d5f832bd466759	1	https://github.com/ridgeworks/clpBNR.git
0.9.12	1a091fd1f0fef5cf10e16e5ed3eb03ce109132c4	6	https://github.com/ridgeworks/clpBNR.git
0.9.13	dfa4e5e71c92423f50c38615cbbc6b59725c29c1	7	https://github.com/ridgeworks/clpBNR.git
0.10.0	d1109bc3f71958bd955a6e32bcb06bd8a60769d7	6	https://github.com/ridgeworks/clpBNR.git
0.10.1	f4f171aa1fd0cc1a90d047b7a1efa79f8e10c26d	6	https://github.com/ridgeworks/clpBNR.git
0.10.2	d97adecb6b020e6ac104869e7e7bc87977cde176	8	https://github.com/ridgeworks/clpBNR.git
0.10.3	f8f70ae0956863112525a19e17043b534349ca98	1	https://github.com/ridgeworks/clpBNR.git
0.10.4	2909fdac5581176005d5db3bbe62bc18399e7f95	12	https://github.com/ridgeworks/clpBNR.git
0.11.0	3f1d7edf5b12a1ae7d51c95606465477497e55f0	9	https://github.com/ridgeworks/clpBNR.git
0.11.1	c30bd15d4bc26c7cea51b1f07b9eff6faec3872f	18	https://github.com/ridgeworks/clpBNR.git
0.11.2	8a041b7dacfc6aa09a22c4d8958934a0d8defbc5	9	https://github.com/ridgeworks/clpBNR.git
0.11.4	c03f9a11c186f1d66647151842e9da3ed5bbd2eb	6	https://github.com/ridgeworks/clpBNR.git
0.11.5	7065160fb6b831d66d6dc1e4450ddafef672aabe	1459	https://github.com/ridgeworks/clpBNR.git
0.11.8	53a8eebbdf2b0d17ebb94663d97411c0821aa415	684	https://github.com/ridgeworks/clpBNR.git
0.11.9	b2c476e078a76dd421f3c10804a49feca644be4a	281	https://github.com/ridgeworks/clpBNR.git
0.11.10	0bf7d4ddfc5b58a22d8a4196f64efa17c4a27fa8	58	https://github.com/ridgeworks/clpBNR.git

CLP(BNR)

clpBNR is an implementation of CLP(BNR) structured as a package for SWI-Prolog. CLP(BNR) is an instance of CLP(R), i.e., CLP over the domain of real numbers. It differs from some other CLP(R)'s in that:

• CLP(BNR) is complete in that any real number can be finitely represented even though the set of reals is infinite. It does this by sacrificing precision: a real number R is represented by an interval (L,U) where L=<R=<U and L and U are numbers as defined by SWI-Prolog (integers, rationals or floats, including the IEEE infinity values). A precise value (L=U) is represented directly by the number.
• CLP(BNR) arithmetic is mathematically sound. Any computed interval will contain the precise value. Due to the well-known pitfalls of IEEE floating point arithmetic, any CLP(R) based on conventional IEEE floating point arithmetic is unsound. (Try: ?- 1.21 =:= 1.1*1.1.) In particular the add and multiply operations are non-associative and non-distributive. Relational interval arithmetic in CLP(BNR) (and some others) ensures that computed intervals contain the mathematically correct real value.
• All constraints, including non-linear constraints are active. In some CLP(R) implementations only linear constraints are active; non-linear constraints are deferred until their set of variables is sufficiently resolved that the constraint becomes linear.
• CLP(BNR) supports an "integral" constraint which forces interval bounds to be integers, enabling constraints over finite domain problems within the relational interval arithmetic framework; booleans can be represented as integer intervals with bounds ((0,1)) and primitives to support boolean logic are included. Including integers and booleans within a single arithmetic framework enables natural solutions to mixed domain problems.
• Implementation: For simplicity and portability reasons, this version of CLP(BNR) is entirely implemented in SWI-Prolog. The main dependencies include attributed variables, support for rationals and IEEE floating point numbers (including rounding modes), and global variables for operational measurements. Versions of clpBNR 0.11.5 and later require SWI-Prolog 9.1.22 or later for properly exported arithmetic functions on intervals. In addition, versions greater than V0.11.0 define an API for users to implement custom interval narrowing operations - see the Reference section of the [Guide to CLP(BNR)][clpBNR_UG] for further details.

  As of version 0.11.4, library(clpBNR) and library(clpBNR_toolkit) are pengine sandbox compliant so they can installed on [SWISH][swish]. Some of the developer centric features, available when running directly on SWI-Prolog, are not available in a sandbox including:

• trace_clpBNR/1 to trace the execution of the fixed point iterator
• watch/2 with the 'trace' option
• custom interval arithmetic primitives are not supported

A Brief Introduction

An interval in CLP(BNR) is a logic variable representing a closed set of real numbers between (and including) a numeric lower bound and upper bound. Intervals are declared using the :: infix operator, e.g.,

?- X::real, [A,B]::real(0,1).
X::real(-1.0e+16,1.0e+16),
A::real(0,1),
B::real(0,1).

Standard practice for outputting attributed variables at the top level is to format them as a (residual) goal. (For narrow real intervals a more compact domain form is used as described below). If bounds are not specified (X above), the defaults are large, but finite, platform dependent values. The infinities (inf and -inf) are supported but must be explicitly specified in the declaration.

To constrain an interval to integer values, type integer can be used in place of real:

?- I::integer, [J,K]::integer(-1,1).
I::integer(-72057594037927936,72057594037927935),
J::integer(-1,1),
K::integer(-1,1).

Finally, a boolean is an integer constrained to have values 0 and 1 (meaning false and true respectively).

?- B::boolean.
B::boolean.

Note that no bounds are displayed for booleans because (0,1) is implicit in the boolean type.

Interval declarations define the initial bounds of the interval which are narrowed over the course of program execution. Narrowing is controlled by defining constraints in curly brackets, e.g.,

?- [M,N]::integer(0,8), {M == 3*N}.
M::integer(0,6),
N::integer(0,2).

?- [M,N]::integer(0,8), {M == 3*N}, {M>3}.
M = 6,
N = 2.

?- [X,Y]::real, {1==X + 2*Y, Y - 3*X==0}.
X:: 0.1428571428571428...,
Y:: 0.428571428571428... .

In the first example, both M and N are narrowed by applying the constraint {M == 3*N}. Applying the additional constraint {M>3} further narrows the intervals to single values so the original variables are unified with the point (integer) values.

In the last example, the constraint causes the bounds to contract almost to a single point value, but not quite. The underlying reason for this is that standard floating point arithmetic is mathematically unsound due to floating point rounding errors and cannot represent all the real numbers in any case, due to the finite bit length of the floating point representation. Therefore all the interval arithmetic primitives in CLP(BNR) round any computed result outwards (lower bound towards -infinity, upper bound towards infinity) to ensure that any answer is included in the resulting interval, and so is mathematically sound. (This is just a brief, informal description; see the literature on interval arithmetic for a more complete justification and analysis.) This example also demonstrates the more compact "ellipsis postfix" form used to output real intervals whose bounds have narrowed so that at least the first 3 digits match. This is not actually a goal but does present the domain in a more readable form. (A strict "goal" format including constraints is supported by enabling a CLP(BNR) environment flag.)

Sound constraints over real intervals (since interval ranges are closed) include ==, =<, and >=, while <>, < and > are provided for integer's. A fairly complete set of standard arithmetic operators (+, -, *, /, **), boolean operators (and, or, xor, nand, nor, ~) and common functions (exp, log, sqrt, abs, min, max and standard trig and inverse trig functions) provided as interval relations. Note that these are relations so {X==exp(Y)} is the same as {log(X)==Y}. A few more examples:

?- {X==cos(X)}.
X:: 0.73908513321516... .

?- {X>=0,Y>=0, tan(X)==Y, X**2 + Y**2 == 5}.
X:: 1.096668128705471...,
Y:: 1.94867108960995... .

?- {Z==exp(5/2)-1, Y==(cos(Z)/Z)**(1/3), X==1+log((Y+3/Z)/Z)}.
Z:: 11.18249396070347...,
Y:: 0.25518872031002...,
X:: -2.0616342622472... .

These examples did not require an explicit :: declaration since the constraints were sufficient to narrow the values to acceptable answers. Internally, any undeclared interval is assigned infinite bounds which often inhibits narrowing possibilities, so it's good practice to always declare intervals with reasonable (or default) bounds values.

It is often the case that the fixed point iteration that executes as a consequence of applying constraints is unable to generate meaningful solutions without applying additional constraints. This may be due to multiple distinct solutions within the interval range, or because the interval iteration is insufficiently "clever". For example:

?- {2==X*X}.
X::real(-1.4142135623730951,1.4142135623730951).

but

?- {2==X*X, X>=0}.
X:: 1.414213562373095... .

In more complicated examples, it may not be obvious what the additional constraints might be. In these cases a higher level search technique can be used, e.g., enumerating integer values or applying "branch and bound" algorithms over real intervals. A general predicate called solve/1 is provided for this purpose. Additional application specific techniques can also be implemented. Some examples:

?- {2==X*X},solve(X).
X:: -1.414213562373095... ;
X:: 1.414213562373095... .

?- X::real, {0 == 35*X**256 - 14*X**17 + X}, solve(X).
X:: -0.847943660827315... ;
X:: 0.0... ;
X:: 0.847943660827315... ;
X:: 0.995842494200498... .

?- {Y**3+X**3==2*X*Y, X**2+Y**2==1},solve([X,Y]).
Y:: 0.39105200...,
X:: -0.92036858... ;
Y:: -0.920368584...,
X:: 0.39105200... ;
Y:: 0.8931356...,
X:: 0.4497874... ;
Y:: 0.449787...,
X:: 0.8931356... ;
false.

Note that all of these examples produce multiple solutions that are produced by backtracking in the top-level listener (just like any other top level query). solve/1 is one of several predicates in CLP(BNR) which "search" for solutions.

Here is the current set of operators and functions supported in this version:

==	is	<>	=<	>=	<	>             %% comparison (`is` synonym for `==`)
+ - * /                               %% basic arithmetic
**                                    %% includes real exponent, odd/even integer
abs                                   %% absolute value
sqrt                                  %% square root (needed?)
min max                               %% min/max (arity 2)
<=                                    %% included (one way narrowing)
and	or	nand	nor	xor	->	,         %% boolean (`,` synonym for `and`)
- ~                                   %% unary negate and not
exp log                               %% exp/ln
sin asin cos acos tan atan            %% trig functions
integer                               %% must be an integer value

Further explanation and examples, including a complete reference section, can be found in the [Guide to CLP(BNR)][clpBNR_UG]. Examples include problems in finite domains, and finding roots, global optima, and boundary value solutions to differential equations. Additional background material is available at [BNR Prolog Papers][bnrpp].

[ia1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.6767 [ia2]: http://fab.cba.mit.edu/classes/S62.12/docs/Hickey_interval.pdf [clip]: https://scholar.lib.vt.edu/ejournals/JFLP/jflp-mirror/articles/2001/S01-02/JFLP-A01-07.pdf [cldl]: http://interval.sourceforge.net/interval/index.html [swip]: http://www.swi-prolog.org [swish]: https://swish.swi-prolog.org/ [bnrpp]: https://ridgeworks.github.io/BNRProlog-Papers [clpBNR_UG]: https://ridgeworks.github.io/clpBNR/CLP_BNR_Guide/CLP_BNR_Guide.html [BNRParchive]: https://github.com/ridgeworks/BNRProlog-Source-Archive

Getting Started

CLP(BNR) is available online on SWISH - no downloading required; see the CLP(BNR) QuickStart Guide%20QuickStart%20Guide.swinb).

If SWI-Prolog has not been installed, see downloads. A current development release or stable release 9.1.22 or greater is required for clpBNR 0.11.5 or later. Earlier versions of clpBNR can run on older versions SWI-Prolog - see README's for those releases for details. (Past releases can be found in the repo "Releases" e.g., https://github.com/ridgeworks/clpBNR/archive/v0.9.2.zip.)

If you do not want to download this entire repo, a package can be installed using the URL `https://github.com/ridgeworks/clpBNR.git`. Once installed, it can be loaded with use_module/1. For example:

?- pack_install(clpBNR,[url('https://github.com/ridgeworks/clpBNR.git')]).
% Cloning into '/Users/rworkman/.local/share/swi-prolog/pack/clpBNR'...
Verify package status (anonymously)
        at "https://www.swi-prolog.org/pack/query" Y/n?
% Contacting server at https://www.swi-prolog.org/pack/query ... ok
% "clpBNR.git" was downloaded 2 times
Package:                clpBNR
Title:                  CLP over Reals using Interval Arithmetic - includes Rational, Integer and Boolean domains as subsets.
Installed version:      0.11.10
Author:                 Rick Workman <ridgeworks@mac.com>
Home page:              https://github.com/ridgeworks/clpBNR
Download URL:           https://github.com/ridgeworks/clpBNR.git
Activate pack "clpBNR" Y/n?
true.

?- use_module(library(clpBNR)).
% *** clpBNR v0.11.10 ***.
%   Arithmetic global flags set to prefer rationals and IEEE continuation values.

Or if the repository has been down downloaded, just consult clpBNR.pl (in `prolog/` directory) which will automatically include helper files in directory clpBNR.

The clpBNR module declaration is:

:- module(clpBNR,          % SWI module declaration
        [
        op(700, xfx, ::),
        (::)/2,                % declare interval
        {}/1,                  % define constraint
        interval/1,            % filter for clpBNR constrained var
        interval_degree/2,     % number of constraints on clpBNR constrained var
        list/1,                % O(1) list filter (also for compatibility)
        domain/2, range/2,     % get type and bounds (domain)
        delta/2,               % width (span) of an interval or numeric (also arithmetic function)
        midpoint/2,            % midpoint of an interval (or numeric) (also arithmetic function)
        median/2,              % median of an interval (or numeric) (also arithmetic function)
        lower_bound/1,         % narrow interval to point equal to lower bound
        upper_bound/1,         % narrow interval to point equal to upper bound

        % additional constraint operators
        op(200, fy, ~),        % boolean 'not'
        op(500, yfx, and),     % boolean 'and'
        op(500, yfx, or),      % boolean 'or'
        op(500, yfx, nand),    % boolean 'nand'
        op(500, yfx, nor),     % boolean 'nor'
        op(700, xfx, <>),      % integer not equal
        op(700, xfx, <=),      % included (one way narrowing)

        % utilities
        print_interval/1, print_interval/2,      % pretty print interval with optional stream
        small/1, small/2,      % defines small interval width based on precision value
        solve/1, solve/2,      % solve (list of) intervals using split to find point solutions
        splitsolve/1, splitsolve/2,   % solve (list of) intervals using split
        absolve/1, absolve/2,  % absolve (list of) intervals, narrows by nibbling bounds
        enumerate/1,           % "enumerate" integers
        global_minimum/2,      % find interval containing global minimum(s) for an expression
        global_minimum/3,      % global_minimum/2 with definable precision
        global_maximum/2,      % find interval containing global maximum(s) for an expression
        global_maximum/3,      % global_maximum/2 with definable precision
        global_minimize/2,     % global_minimum/2 plus narrow vars to found minimizers
        global_minimize/3,     % global_minimum/3 plus narrow vars to found minimizers
        global_maximize/2,     % global_maximum/2 plus narrow vars to found maximizers
        global_maximize/3,     % global_maximum/3 plus narrow vars to found maximizers
        nb_setbounds/2,        % non-backtracking set bounds (use with branch and bound)
        partial_derivative/3,  % differentiate Exp wrt. X and simplify
        clpStatistics/0,       % reset
        clpStatistic/1,        % get selected
        clpStatistics/1,       % get all defined in a list
        watch/2,               % enable monitoring of changes for interval or (nested) list of intervals
        trace_clpBNR/1         % enable/disable tracing of clpBNR ops
        ]).

Also included with this pack is module clpBNR_toolkit, a collection of useful utilities for global optimization problems or the use "meta-contractors" to improve performance. Reference documentation and examples of use are included in the User Guide ([Guide to CLP(BNR)][clpBNR_UG]).

SWI-Prolog Environment Flags

This package sets the SWI-Prolog arithmetic global environment flags as follows:

set_prolog_flag(prefer_rationals, true),           % enable rational arithmetic
set_prolog_flag(max_rational_size, 16),            % rational size in bytes before ..
set_prolog_flag(max_rational_size_action, float),  % conversion to float

set_prolog_flag(float_overflow,infinity),          % enable IEEE continuation values
set_prolog_flag(float_zero_div,infinity),
set_prolog_flag(float_undefined,nan),

The setting of these flags occurs when the first clpBNR attributed variable in a thread is created. This package will not work as intended if these flag values are not respected.

Example output in the documentation is premised on flag write_attributes is set to portray. This (thread-local) flag will be set accordingly when the arithmetic flags are set but nothing prevents it from being subsequently overwritten (as is the case with any global flag).

Contents of pack "clpBNR"

Pack contains 72 files holding a total of 3.0M bytes.