Sampling algorithm

[Mauro DiNuzzo]

Hello, Prolog world!

By using CLP one can easily obtain the domain of the variables.

The exact solutions can be obtained by the labeling process. However,
if there is a large number of variables, this labeling process can be
very time-consuming.

I am wondering if there is some sampling algorithm (preferably in
Prolog) which could be used in conjunction with CLP to sample the
solution space, thereby obtaining a distribution of the variables.

Any help will be very appreciated.

Thank you very very much.

Mauro DiNuzzo

[Jan Burse]

Mauro DiNuzzo schrieb:

> I am wondering if there is some sampling algorithm (preferably in
> Prolog) which could be used in conjunction with CLP to sample the
> solution space, thereby obtaining a distribution of the variables.

Could you be more specific about the sampling
you desire? I guess something can be done in
the labeling phase. For example if the
labeling sees at some stage only:

x1 in D1
..
xn in Dn

And no more other suspended constraints, then
this could give rise a sampling of an area
D1 x ... x Dn. So it would be eventually faster
than waiting for its labeling and sample pointwise.

Bye

[Mauro DiNuzzo]

Assume working with CLP(R).

You have N variables (X1,...,XN).
You set some constraints on them, eventually obtaining the domains
that satisfy those constraints (D1,...,DN).

Here I would like to sample the space of solution (S1 in D1,...,SN in
DN) that satisfy the constraints. The domains themselves do not say
nothing about the exact solutions.

Since we are in CLP(R) we have no labeling predicate.
However, we can divide each domain in M discrete values and do a sort
of "generate and test". This is a brute-force sampling algorithm, that
possibly maps the solutions by spanning the domains of the variables.
But I cannot figure out the relevance of this sampling.

For example, you have to define an order of the variables (assume from
X1 to XN). You start "labeling" X1, then X2 and so on. At a certain
point, assume XK (with K<N), the other N-K variable will be eventually
set to a specific solution. These latter values likely are outside the
discrete values that you have divided their domains in.

Thus, my motivation is to ask for already existing (and tested)
sampling strategy of real variables with upper and lower bounds (i.e.
a domain). I was thinking about Monte Carlo sampling (do you know if
this has been already implemented in Prolog?).

Feel free to ask me further.

Thank you very much.
M