Clpr

Help!
1

Experimenting with clpr.
Suppose I have two circles with radii R1 and R2 and centers AX,AY and BX,BY respectively, then I should be able to find their intersection


circles :-
    R1 = 5,
    R2 = 5,
    AX = 0,
    AY = 3,
    BX = 3,
    BY = 5,
    {(CX - AX)*(CX - AX)+ (CY-AY)*(CY-AY) =:= R1*R1},
    {(CX - BX)*(CX - BX)+ (CY-BY)*(CY-BY) =:= R2*R2},
    maximize(CX),
    maximize(CY).

but the maximize(CX) call fails.

It works for linear solution

linear :-
    {AY =:= 2*AX - 2, AY =:= -AX + 3},
    maximize(AX),
    maximize(AY).

Anybody who’s delved into clpr? it’s just the thing for what I need, but am I fundamentally misunderstanding something?

1 Like
2

CLP® is based on the simplex algorithm, which is limited
to linear constraints. An extension to quadratic constraints,
QUAD-CLP®, has been proposed in the 1990’s, and I seem to
remember I have been able to play with it.
Kind regards,

Roberto
2 Likes
3

Hey, thanks! OK, so everything has to be linear?

4

You can use non-linear constraints, and can be eventually solved if they become linear via instantiation.

1 Like
5

Here’s a list with a little more details about this: SWI-Prolog -- Manual

1 Like
6

As a bit of an ongoing hobby I’ve been working on a version of CLP(R) based on interval arithmetic. A version was originally implemented as CLP(BNR) (Booleans, Naturals, Reals) some 30 years ago. Similar systems of the same era or a little later include CLIP (Tim Hickey et. al. at Brandeis U.), Newton, and Numerica (Pascal van Hentenryk et.al., which I think was subsumed by ILOG Solver). This version is written entirely in SWI-Prolog (no “foreign” code) and is available as package clpBNR, although it’s still somewhat of a work in progress.

A version of the circles problem in CLP(BNR):

?-  {X**2 + (Y-3)**2 == 25, (X-3)**2 + (Y-5)**2 == 25}, solve([X,Y]).
X:: -1.0869494955077...,
Y:: 7.8804242432615... ;
X:: 4.0869494955077...,
Y:: 0.11957575673840... .

Note that the answers aren’t floating point numbers; they’re intervals (attributed variables) represented by a lower and upper bound which contain the “real” answer which, in general, isn’t a precise floating point value. (The ellipsis format shown displays common digits of both bounds with ... suffix.) Unlike floating point arithmetic, interval arithmetic strives to be mathematically sound:

?- 1.21 is 1.1*1.1.
false.

?- {1.21 is 1.1*1.1}.
true.

As shown with the example, non-linear constraints are active (rather than being deferred pending satisfaction of linearity), which can be quite powerful:

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

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

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

So just a sample. I’m still exploring possibilities and limitations. For example, although it can deal with linear systems:

?- [AX,AY]::real,{AY =:= 2*AX - 2, AY =:= -AX + 3}.
AX:: 1.666666666666666...,
AY:: 1.333333333333333... .

It may not scale particularly well. But many of these kinds of issues can be addressed in combination with symbolic approaches (e.g., gaussian pivoting for linear systems).

6 Likes
7

Anne, take a look to

?- pack_install(clpBNR).

Most likely will solve your problem, and the documentation page is anyway a good reading.

2 Likes
8

Well, that’s quite amazing! Far out, solves my problem I think.

:: Annie is here, dancing about like somebody gave her too much sugar. She calms down, and is happily playing with clpBNR::

  • Thanka Uncle Rick!
9

this is just ridiculously powerful and fun.
One non obvious thing - the solve produces intervals - you can convert them back to real live numbers with midpoint (kind of wish there was a conversion to a pair of upper/lower bounds).

10

Also BNR = Bell Northern Research (roughly, the Canadian equivalent of Bell Labs).
It’s interesting that two telco research groups - Northern Telecom (through BNR) and Ericsson - did quite a bit of work on Prolog and related programming languages. (I was at BNR when Bell Labs came out with Unix for telephone switches and we thought they were crazy to use Unix and C for high reliability systems.)

2 Likes
11

Happy to hear to looks promising. Feel free to use “Issues” at GitHub - ridgeworks/clpBNR_pl: CLP(BNR) module for SWI-Prolog for any problems/requests.

Not sure what you mean by “a conversion to a pair of upper/lower bounds”, perhaps range/2 ?

?- X::real(1,10), range(X,R).
R = [1, 10],
X::real(1, 10).
1 Like
12

Yes, that was where I first encountered this technology, but I was too pre-occupied building protocol stacks in Prolog to spend much time with it.

And I do remember you, Peter, from DMS Field Trial days. (PROTEL not Prolog.)

13

Protel was definitely better than C. :wink:
And SOS (Switch Operating System) was better than Unix.

I thought your name was familiar, Rick … but my memory is dim about things so long ago. I found a few familiar names at Prolog and Logic Programming Historical Sources Archive — Software Preservation Group (including my DMS manager, Peter Cashin).

1 Like
14

Rick, I like your system. I have to confess, I pulled it out because I really was solving a fairly simple problem and kept running into struggles. But it’s obviously just still a work in progress. as soon as the craziness of current project slows down I’ll try to submit a good test case.