Browse Groups

• ## Choosing real numbers with certain characteristics (CSP or local search?)

(1)
• NextPrevious
• 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
Message 1 of 1 , Sep 10, 2010
View Source

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 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?

Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.