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