0

Be $A \subset D \wedge m \in D \wedge \forall x \in A:x < m$, with $D$ finite and included in the positive integers, I need to partition $A$ into $B_n$, while minimizing $n$, so that $$\left(\sum_{i\in B_n}i\right) \leq m$$

I also know that $\max(A) < \frac{m}{2}$, consecuently $m > \max(A) + \min(A)$, so trivial cases are not interesting.

Ismael Luceno
  • 101
  • 3
  • 1
    What if $A$ contains $m+1$? Do you add the assumption that such a covering exists? Furthermore, why can't you take $B_1=A$ and $n=1$? – zarathustra Jul 22 '14 at 14:30
  • Even after the edit: this problem has a solution iff $(\sum_{i\in A} i) < m$, and in this case the optimal value of $n$ is $1$. – zarathustra Jul 22 '14 at 14:34
  • The trivial case is not so interesting because it rarely happens, $A$ consists of experimental data... – Ismael Luceno Jul 22 '14 at 14:43
  • What is the question then? Your question is "minimize the number of subsets", and it appears that the solution is always $1$, provided that the problem has a solution in the first place. Trivial or not, this is the optimal solution. – zarathustra Jul 22 '14 at 14:45
  • 1
    The question is nontrivial if $\sum_{i \in A} i \ge m$. For example with $m=5$ and $A = {1,2,3,4}$, an optimal solution is ${1,3},{2},{4}$. – Robert Israel Jul 22 '14 at 14:52
  • Oh, my bad, I read the equation has the sum for all the $B_n$, which is the sum of $A$, and of course it was silly. Sorry about that! – zarathustra Jul 22 '14 at 16:20

1 Answers1

1

EDIT:

You're partitioning $A$ into disjoint subsets $B_j$, each with sum $<m$. I'll assume for simplicity all members of $A$ are integers.

Suppose you know you can do it with $N$ subsets. Let $x_{ij}$, $i \in A$, $j \in \{1,\ldots,N\}$, be a binary variable: interpret $x_{ij} = 1$ to mean $i$ is in set $B_j$, $x_{ij} = 0$ that it is not in $B_j$. Let $y_j$, $j=1\ldots,n$ be a binary variable: interpret $y_j = 1$ to mean set $j$ is used. Then you have constraints $$ \eqalign{\sum_i i x_{ij} \le (m-1) y_j & \forall j\cr \sum_j x_{ij} = 1 & \forall i\cr y_{j+1} \le y_{j} & \forall j \in \{1,\ldots,N-1\}\cr x_{ij} , y_j\in \{0,1\} & \forall i,j\cr}$$ and you want to minimize $\sum_j y_j$.

Give it to an integer linear programming solver. If the problem is too big for that, you might try heuristic methods such as simulated annealing or tabu search.

Robert Israel
  • 448,999