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

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/