From: Marco Gavanelli <marco.gavanelli_at_unife.it>

Date: Wed, 12 Sep 2007 11:47:39 +0200

Received on Wed Sep 12 2007 - 10:47:43 CEST

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

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*