<p>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.</p>

<p>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 &lt; f( { r_0, r_1, \dots, r_{k-1} } ) &lt; \epsilon$, then this is essentially the number partition problem.  </p>

CC BY-SA 2.5
2010-09-09T01:59:34.283Z
2010-09-09T01:59:34.283Z
user834
<p>I have a set of n real numbers. I also have a set of functions,</p>

<pre><code>f_1, f_2, ..., f_m.
</code></pre>

<p>Each of these functions takes a list of numbers as its argument. I also have a set of m ranges,</p>

<pre><code>[l_1, u_1], [l_2, u_2], ..., [l_m, u_m].
</code></pre>

<p>I want to repeatedly choose subsets {r_1, r_2, ..., r_k} of k elements such that</p>

<pre><code>l_i &lt;= f_i({r_1, r_2, ..., r_k}) &lt;= u_i for 1 &lt;= i &lt;= m.
</code></pre>

<p>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. </p>

<p>These are the m constraints that I need to satisfy.</p>

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

<p>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.</p>

<p>Is there a way to do this?</p>

<p>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)?</p>

<p>[Note that <a href="https://cstheory.stackexchange.com/questions/1089/constraint-satisfaction-problem-choosing-real-numbers-with-variance-in-a-certain">this question</a> is a special case.]</p>

CC BY-SA 2.5
2010-09-08T20:49:24.537Z
You can use Latex math (inside a pair of $-signs) to make your question easier to read.
Jukka Suomela
<ds.algorithms><st.statistics>
Constraint Satisfaction Problem: Choosing real numbers with certain characteristics
Paul Reiners
# Constraint Satisfaction Problem: Choosing real numbers with certain characteristics

(Asked by: username_0 on 2010-09-08)

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

**Tags:** ds.algorithms, st.statistics

> **Comments:**
> **username_1**: You can use Latex math (inside a pair of $-signs) to make your question easier to read.  

---

## 1 answers

### Answer by username_2 on 2010-09-09. Score: 2 | Accepted answer

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.


---

