Constraint Satisfaction Problems Again

Appeared in Volume 8/1, February 1995

Keywords: constraints.

wbradley@pumpkin.ece.uc.edu
William Bradley
1st September 1994

Is anyone out there doing work in general or binary CSP with non-finite domains? Most CSP techniques I'm familiar with are search-based, and this won't work if you can't enumerate a variable's domain.

I'm using Tsang's book (very nice, in my opinion) as an overview, but he doesn't discuss infinite-domain CSPs beyond the use of constraint propagation in real-valued linear systems.

puget@corvisart.ilog.fr
Jean-Francois Puget
2nd September 1994

Although floating point intervals are finite (*), you may be interested in CLP systems using floating point valued variables, whose domains are represented by intervals, such as Interlog, Ilog Solver, Cial, CLP(BNR).

(*) The number of floating point values is finite on any computer, even if you consider two additional values for -inf and +inf.

Interlog and Ilog Solver use similar techniques, described in:

O. Lhomme. `Consistency Techniques for numeric CSPs', Proc. IJCAI93, Chambery, France, pp 232-238.

A paper on CLP(BNR) is:

W.J. Older and A. Vellino, `Constraint Arithmetic on Real Intervals', Constraint Logic Programming: Selected Research, MIT Press, 1993.

Although these domains are finite, the usual way to search for solutions is not to enumerate the values, but to use a domain-splitting approach.

To conclude, I give an example in Ilog Solver. Let us code the polynom:

$(x + 1)(x + 2)...(x + 20) + 2^{-23}x^{19}$

This example can be coded as follows:

CTGOAL1(PrintFail, CtFloatVar&, x){
    cout <<  x << endl;
}

int main () {
  CtInit();
  CtFloatVar x (-1e10, 1e10); x.setName("x");
  CtEq((x + 1.)*(x + 2.)*(x + 3.)*(x + 4.)*(x + 5.) *
     (x + 6.)*(x + 7.)*(x + 8.)*(x + 9.)*(x + 10.) *
     (x +11.)*(x + 12.)*(x + 13.)*(x + 14.)*(x + 15.) *
     (x +16.)*(x + 17.)*(x + 18.)*(x + 19.)*(x + 20.) +
     pow(2., -23.0)*CtPower(x, 19L),
     0.);
  CtSolveBounds(x, 1e-5); // preprocessing
  CtSolveAll(CtAnd(CtInstantiate(x), // search
                 Print(x)));
  CtEnd();
  return 0;
}

This program prints all the roots of this equation;

x[-1..-1]
x[-2..-2]
x[-3..-3]
x[-4..-4]
x[-5..-5]
x[-6.00001..-6.00001]
x[-6.9997..-6.9997]
x[-8.00727..-8.00727]
x[-8.91725..-8.91725]
x[-20.8469..-20.8469]

jlee@cs.cuhk.hk
Jimmy Ho Man Lee
1st September 1994

The following two publications might help:

Lee, J.H.M. and van Emden, M.H., 'Interval Computation as Deduction in CHIP', Journal of LP, 1993, Vol. 16, No. 3 & 4, pp.255 - 276

Chiu, C.K. and Lee, J.H.M., 'Towards Practical Interval Constraint Solving in LP', LP: Proc. of the 1994 Int. Symp., 1994

An improved version of the CIAL system described in the second paper is available via FTP. Interested parties can contact cial@cs.cuhk.hk.

No Next