From: Fred Gilham
Subject: Re: Numerical constraint solver
Date: 
Message-ID: <u7it6fre6o.fsf@snapdragon.csl.sri.com>
Drew McDermott <··············@yale.edu> writes:

> <!doctype html public "-//w3c//dtd html 4.0 transitional//en">
> <html>
> Can anyone point me to a package (in Lisp, of course) for solving numerical
> constraints?&nbsp; It has to handle multi-variable linear constraints,
> but if it also handled some nonlinear ones that would be nice.&nbsp; The
> number of variables is probably quite low, &lt;20, so major horsepower
> is not required.&nbsp; A straightforward implementation of the simplex
> algorithm would work fine.&nbsp; I just don't want to write it.
> <p>Thanks.
> <p>&nbsp; -- Drew McDermott
> <br>&nbsp;</html>
> 

You may want to look at SCREAMER.  It says,

     ...The constraint handling mechanism used in SCREAMER was adapted
     from the one used in CHiP (Van Hentenryck, 1989).  The novel
     approach taken by CHiP and SCREAMER is to combine backtracking
     search with constraint propagation to yield a complete constraint
     solver.  Unlike CHiP which uses linear programming techniques to
     solve systems of numeric constraints, SCREAMER uses range
     propagation and supports a divide and conquer approach to solving
     nonlinear numeric constraint problems.....


-- 
Fred Gilham                                   ······@csl.sri.com
I was storing data in every conceivable way, including keeping a chain
of sound waves running between the speaker and the microphone. There
was no more memory left to be had....
From: Arseny Slobodjuck
Subject: Re: Numerical constraint solver
Date: 
Message-ID: <3cc96015.2269623@news.vtc.ru>
On 25 Apr 2002 08:27:43 -0700, Fred Gilham
<······@snapdragon.csl.sri.com> wrote:

>> Can anyone point me to a package (in Lisp, of course) for solving numerical
>> constraints?&nbsp; It has to handle multi-variable linear constraints,
>> but if it also handled some nonlinear ones that would be nice.&nbsp;
>You may want to look at SCREAMER.  It says,
>
>     ...The constraint handling mechanism used in SCREAMER was adapted
>     from the one used in CHiP (Van Hentenryck, 1989).  The novel
>     approach taken by CHiP and SCREAMER is to combine backtracking
>     search with constraint propagation to yield a complete constraint
>     solver.  Unlike CHiP which uses linear programming techniques to
>     solve systems of numeric constraints, SCREAMER uses range
>     propagation and supports a divide and conquer approach to solving
>     nonlinear numeric constraint problems.....

There is also 'Delta Blue' algorithm implementation:
(I didn't dare to see it much closely yet).

***** A Common Lisp Implementation of the Delta Blue algorithm *****

delta-blue.lisp implements the Delta Blue incremental constraint
satisfaction system using a constraint hierarchy with a
local-predicate-better comparator.  This code was translated directly
from the pseudocode in the appendix to UW CS TR 91-08-12 ``Using
Constraints for User Interface Construction'' by John Maloney, using
similar function and variable names.  Refer to the pseudocode for
detailed comments.  This file contains comments where the code is
changed significantly from the pseudocode.

examples.lisp contains a few functions for constructing simple
constraints,
and some test programs.

  ~~ Michael Sannella
     December 19, 1991