# Re: [eclipse-users] as I can generate problems (CSP) random in Eclipse

From: Marco Gavanelli <marco.gavanelli_at_...17...>
Date: Wed, 12 Sep 2007 11:47:39 +0200
```Miguel A. wrote:
>
> hi...
>
> as I can generate problems (CSP) random in Eclipse.
> something like…
>
> solve (Vars): -
>         model_random (Vars, %parameters,...),
>         search (Vars),
>         print_solution (Vars).
>
>
> I need to know like implementing the predicate model_random/   ?
>
> bye..

Dear Miguel,

some time ago I have developed this random CSP generator in ECLiPSe. I
cannot ensure it is bug-free (I cannot even find if it is the last
version, sorry), it has very few comments and they are in Italian. So it
is not very valuable, but since you did not get better answers, I
thought it might be of some use.

In the literature, a CSP is usually generated with 4 parameters; I used
the following:
- N (number of variables)
- D (size of domains)
- P (probability that there exists a constraint between two variables)
- Q (conditional probability that, given that there is a constraint
between two variables X and Y, an assignment X<-v, Y<-w is consistent).

In general, there are different methods for generating random CSPs. The
attached program uses the so-called "model-A", in which for each pair of
variables you flip a coin (that has probability P of giving Head and 1-P
of giving Tails), and if it is Head, you add a constraint between the
two variables. Same for consistent assignments.

Of course, this model does not ensure you that the frequency of
constraints is equal to the probability P: you might use P=90% and be
very unlucky and get a CSP without any constraint.

Usage:
generate(3,4,50,90) will generate a CSP with 3 variables, domains
cardinality=4, P=50% and Q=90%.

Constraints are recorded in facts constraint/2. E.g.,

constraint(1,2).

means that there is a constraint between the first and the second variable.

The extension of constraints is recorded in facts consistent/4.

constraint(1,2,0,[1,3]).

means that if you assign value 0 to the first variable, then for the
second the consistent values are 1 and 3 (according to the constraint
between variables 1 and 2).

In order to solve the CSP, you can use the following predicate:

:- lib(fd).
:- lib(propia).

solve(N,D,L):-
length(L,N),
D1 is D-1,
L :: 0..D1,
(for(I,1,N),foreach(X,L), param(N,L) do
(for(J,1,N), foreach(Y,L), param(X,I) do
((constraint(I,J); constraint(J,I))
-> writeln(constraint(I,J)),
(consistent(I,J,X,LY), member(Y,LY) ) infers most
;  true
)
)
),
labeling(L).

For example:

[eclipse 6]: generate(2,3,50,80).
gen

Yes (0.00s cpu)
[eclipse 7]: solve(2,3,L).

L = [0, 1]
Yes (0.00s cpu, solution 1, maybe more) ? ;

L = [0, 2]
Yes (0.01s cpu, solution 2)
[eclipse 8]: listing.

consistent(1, 1, 0, [0]).
consistent(1, 1, 1, [1]).
consistent(1, 1, 2, [2]).
consistent(2, 2, 0, [0]).
consistent(2, 2, 1, [1]).
consistent(2, 2, 2, [2]).
consistent(2, 1, 1, [0]).
consistent(1, 2, 0, [2, 1]).
consistent(2, 1, 2, [0]).

constraint(1, 2).

function(0 + s(0)).
function(0 + s(0)).

Yes (0.02s cpu)

Cheers,
Marco

--
Marco Gavanelli, Ph.D.
Computer Science Division
Dipartimento di Ingegneria
University of Ferrara
Via Saragat 1 - 44100 Ferrara (Italy)
Tel  +39-0532-97-4833
Fax  +39-0532-97-4870
http://www.ing.unife.it/docenti/MarcoGavanelli/

```
• application/x-perl attachment: gen.pl
Received on Wed Sep 12 2007 - 10:47:43 CEST

This archive was generated by hypermail 2.3.0 : Tue Aug 06 2024 - 21:13:20 CEST