Send EmailI 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 m ranges,
[l_1, u_1], [l_2, u_2], ..., [l_m, u_m].
I want to repeatedly choose a subset {r_1, r_2, ..., r_k} of k elements (from the pool of n numbers) 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 change
f_i({r_1, r_2, ..., r_k})
by much. average and variance are two f_i that are commonly used.
These are the m constraints 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 k that 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 that f_i (for any i) can be computed in a constant amount of time.)
Note that n is large enough that I cannot brute-force the problem. That is, I cannot just iterate through all k-element subsets and find which ones satisfy the m constraints.
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 f is the average function. Then f of 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?
