Constraint Satisfaction Problems (CSP) w/ non-finite domains?
Author Message
Constraint Satisfaction Problems (CSP) w/ non-finite domains?

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, IMHO) as an overview, but he doesn't
discuss infinite-domain CSPs beyond the use of constraint propagation
in real-valued linear systems.  This doesn't help me much...

Help, anyone?

Bill

P.S.  Has there been any work done on feedback-free searches over
non-finite domains (via domain restriction, perhaps)?

--
Bill Bradley                            Elec./Comp. Eng. Dept.

Sun, 16 Feb 1997 20:35:59 GMT
Constraint Satisfaction Problems (CSP) w/ non-finite domains?

Quote:

>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, IMHO) as an overview, but he doesn't
>discuss infinite-domain CSPs beyond the use of constraint propagation
>in real-valued linear systems.  This doesn't help me much...

>Help, anyone?

>Bill

>P.S.  Has there been any work done on feedback-free searches over
>    non-finite domains (via domain restriction, perhaps)?

How about looking at Operation Research?

Alex Kean
-------------------------------------------------------------------------

The Hong Kong University of Science & Technology     Tel: (852) 358-6992
Clear Water Bay, Kowloon, HONG KONG                  Fax: (852) 358-1477
-------------------------------------------------------------------------

Mon, 17 Feb 1997 09:41:07 GMT
Constraint Satisfaction Problems (CSP) w/ non-finite domains?

Quote:

>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, IMHO) as an overview, but he doesn't
>discuss infinite-domain CSPs beyond the use of constraint propagation
>in real-valued linear systems.  This doesn't help me much...

The following two publications might help:

author = {Lee, J.H.M. and van Emden, M.H.},
title = {Interval Computation as Deduction in {CHIP}},
journal = {Journal of Logic Programming},
year = 1993,
volume = 16,
number = {3 \& 4},
pages = {255--276}
}

author = {Chiu, C.K. and Lee, J.H.M.},
title = {Towards Practical Interval Constraint Solving in Logic Programming},
booktitle = {Logic Programming: Proceedings of the 1994 International Symposiu
m},
year = 1994
}

The CIAL system described in the second paper is available for FTP.

Cheers,
jim

Mon, 17 Feb 1997 17:17:52 GMT
Constraint Satisfaction Problems (CSP) w/ non-finite domains?

Quote:

>>Is anyone out there doing work in general or binary CSP with non-finite
>>domains?

>How about looking at Operation Research?

How about looking at Constraint Logic Programming ! For example, for the
domain of the real numbers, with linear equations and inequalities, the
simplex algorithm can be embedded in a Logic Programming language. The
reals are the best-known example of an infinite domain, but by no means
the only one. Example systems include CLP(R) from IBM, and Eclipse from
ECRC for the domain of rational numbers.

Look in the FAQ for this newsgroup for details on CLP(R), Eclipse, some
papers you can read etc.

Quote:
>> Most CSP techniques I'm familiar with are search-based, and
>> this won't work if you can't enumerate a variable's domain.

Of course. Search is the worst possible thing to do (unless you have no
alternative). If there is no well-known algorithm for a particular
domain, one can use interval methods, which are approximate. See e.g.
Echidna or CLP(Intervals) in the FAQ.

Michael Jampel

Mon, 17 Feb 1997 22:38:51 GMT
Constraint Satisfaction Problems (CSP) w/ non-finite domains?
|>
|> 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, IMHO) as an overview, but he doesn't
|> discuss infinite-domain CSPs beyond the use of constraint propagation
|> in real-valued linear systems.  This doesn't help me much...
|>
|> Help, anyone?
|>
|> Thanks in advance,
|> Bill

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 :

\bibitem [Lho 93] {lho93} O. Lhomme
Consistency Techniques for numeric CSPs''
{\em Proc. IJCAI93}, Chambery, France, pp 232-238.

A paper on CLP(BNR) is:

\bibitem [OV 93] {ov93}  W.J. Older and A. Vellino.
Constraint Arithmetic on Real Intervals'',
{\em Constraint Logic Programming: Selected Research},
MIT Press, 1993 .

CIAL papers are available but I don't have exact references here.

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:

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

Quote:
}

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;
Quote:
}

\end{verbatim}

This program prints all the roots of this equation;

\begin{verbatim}
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]
\end{verbatim}

I hope this helps.

Jean-Francois

--

ILOG S.A.
2 Avenue Gallieni - BP 85      tel : (33 1) 46 63 66 66
94253 Gentilly Cedex FRANCE    fax : (33 1) 46 63 15 82

Tue, 18 Feb 1997 17:04:54 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages