I have a set (or pool) of *n *real numbers. I also have a set of *m *functions,

`f_1, f_2, ..., f_m.`

Each of these functions takes a list of numbers as its argument. I also have a set of

mranges,`[l_1, u_1], [l_2, u_2], ..., [l_m, u_m].`

I want to

repeatedlychoose a subset{r_1, r_2, ..., r_k}ofkelements (from the pool ofnnumbers) such that`l_i <= f_i({r_1, r_2, ..., r_k}) <= u_i for 1 <= i <= m.`

Note that the functions are smooth. Changing one element in

{r_1, r_2, ..., r_k}will not changef_i({r_1, r_2, ..., r_k})

by much. average and variance are two

f_ithat are commonly used.These are the

mconstraints that I need to satisfy.Moreover I want to do this so that the set of subsets I choose is uniformly distributed over the set of all subsets of size

kthat satisfy these m constraints. Not only that, but I want to do this in an efficient manner. How quickly it runs will depend on the density of solutions within the space of all possible solutions (if this is 0.0, then the algorithm can run forever). (Assume thatf_i(for anyi) can be computed in a constant amount of time.)Note that

nis large enough that I cannot brute-force the problem. That is, I cannot just iterate through allk-element subsets and find which ones satisfy themconstraints.Is there a good way to do this?

I'm starting to think this is not a true CSP. This is because partial assignments can violate a constraint while an extension of such a partial assignment might be consistent. For example, if

fis the average function. Thenfof some set of numbers from the pool might not fall within the range, while, if you add more numbers from the pool, it will. Is it true that this not a CSP problem and not amenable to CSP solutions?I'm starting to think this is best solved by local search. I've implemented hill climbing and simulated annealing, but, so far, just repeatedly guessing solutions until you find one that is satisfactory is working faster than either hill climbing or simulated annealing.

Bringing this around to the book, are the techniques described in Section 4.1 the best techniques to try using for this problem or should I be trying some techniques given elsewhere in the book?