1
$\begingroup$

I have a set of n real numbers. I also have a set of 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 subsets {r_1, r_2, ..., r_k} of k elements 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.

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).

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 way to do this?

What sorts of techniques are commonly used for a CSP like this? Can someone point me in the direction of good books or articles that talk about problems like this (not just CSPs in general, but CSPs involving continuous, as opposed to discrete values)?

[Note that this question is a special case.]

$\endgroup$
  • 4
    $\begingroup$ You can use Latex math (inside a pair of $-signs) to make your question easier to read. $\endgroup$ – Jukka Suomela Sep 8 '10 at 20:49
2
$\begingroup$

This problem is clearly NP-Complete, so finding an efficient solution is almost surely out of the question. Since you've put no real constraints on $f_i$, the best general solution is probably a brute force search. If you knew something more about the $f_i$ then maybe you could exploit that to cull the search space or even come up with an efficient algorithm, but in general, even for simple functions this problem is difficult.

For example, choose just one function, $f( { r_0, r_1, \dots , r_{k-1} } ) = \sum_{i=0}^{k-1} r_i $, with the constraint $ -\epsilon < f( { r_0, r_1, \dots, r_{k-1} } ) < \epsilon$, then this is essentially the number partition problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.