3
$\begingroup$

I am trying to solve the following:

Given a set $S_0$, find min $|S|$ where $S_0 \subseteq S$ subject to:

$\forall s \in S$ $\exists$ $s_a, s_b \in S $ $|$ $ ( s_a \neq s, s_b\neq s ) \land ( s = s_a + s_b \lor s = 1 \lor s=2 ) $

Or in english, forall s in S there exists sa, sb in S such that sa != s, sb != s AND ( s = sa + sb OR s = 1 OR s = 2 )

For example if $S_0 = \{ 7, 9, 13, 22 \}$ then the solution is $S = \{ 1, 2, 3, 4, 7, 9, 13, 22 \}$ as

1 -> is 1 so allowed
2 -> is 2 so allowed
3 = 1 + 2
4 = 1 + 3
7 = 3 + 4
9 = 7 + 2
13 = 9 + 4
22 = 9 + 13
|S| = 8

$|S_0|$ is not particularly large but the numbers in $S_0$ can be very very large such that expressing all numbers possible is infeasible.

I have tried an ILP and ran out of memory expressing the binary variables for each number in the set.

My current approach ( which gives a pretty bad solution ) is pick the lowest number that is violated, heuristically pick two numbers and put them in the set. Repeat until all numbers meet constraints.

An approximate solution is fine. Anyone have any ideas?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! What's the best solution you've found so far? How large is the largest number in $S_0$, for the size of problem you have to deal with in your situation? $\endgroup$ – D.W. Nov 4 '16 at 5:16
  • $\begingroup$ Can $s_a = s_b$? $\endgroup$ – Arthelais Nov 4 '16 at 5:23
  • $\begingroup$ @D.W. My actual problem has more complicated constraints, but i would say $|S_0|$ isn't particularly large but the number is $S_0$ can be very large ( many many add combinations ). It is infeasible to explore or even store the possibilities. Trying to translate my method i would say it heuristically proposed two candidates for the lowest number which was violated and added them until no violations. $\endgroup$ – da_steve101 Nov 4 '16 at 5:24
  • $\begingroup$ @Arthelais yes should be fine $\endgroup$ – da_steve101 Nov 4 '16 at 5:26
2
$\begingroup$

I suggest you formulate this as an instance of integer linear programming (ILP). Let $m$ be the largest number in $S_0$. For each $i$ such that $1 \le i \le m$, introduce the zero-or-one variable $x_i$, with the intended meaning that $x_i=1$ means that $i \in S$ and $x_i=0$ means that $i \notin S$.

Now your constraints can be readily converted into linear inequalities: e.g., for each $s$ such that $2<s \le m$, we obtain that $x_s=1$ implies $\lor_{s_a,s_b} (x_{s_a}=1 \land x_{s_b}=1)$, where the disjunction is taken over all $s_a,s_b$ such that $1 \le s_a < s$ and $1 \le s_b < s$. This can be converted into a linear inequality; see Express boolean logic operations in zero-one integer linear programming (ILP). Also, for each $i \in S_0$, we add the requirement $x_i=1$. Finally, we minimize $\sum_i x_i$. Feeding this to an off-the-shelf ILP solver should yield a solution.

This should find the exact optimal solution, as long as the largest number in $S_0$ is not too large. However, the running time is potentially exponential in $m$, the largest number in $S_0$. I don't know if there is a polynomial-time solution.

(You could also formulate it as an instance of SAT instead of ILP. This will require applying the Tseitin transform to convert the implication/disjunction into CNF, and it will require constructing an adder-circuit to add the requirement that the size of $S$ is at most $k$ and then doing binary search over $k$. Then, you could feed it to an off-the-shelf SAT solver. I have no idea whether this will work better than the ILP approach.)

$\endgroup$
  • $\begingroup$ I have tried an ILP. The problem is so large that all the binary variables don't fit in memory ( of smallish computer though ). $\endgroup$ – da_steve101 Nov 4 '16 at 5:33
  • $\begingroup$ Good answer though :) I can't upvote :/ $\endgroup$ – da_steve101 Nov 4 '16 at 5:42
  • $\begingroup$ Thought about it a bit more, think I might be able to mix them. Think I can generate a reasonable subset of them and use ILP from there. Thanks :) $\endgroup$ – da_steve101 Nov 4 '16 at 10:47
2
$\begingroup$

If you list the numbers in increasing order, then this is the problem of finding a minimum-length addition chain. According to that article, this problem was proved NP-complete here for a set of numbers (as in your case), though it appears the complexity status is still open for a single number.

The Wikipedia page also gives links to some other articles, for example this one, whose abstract says that they can compute optimal addition chains for all $n \le 2^{32}$.

$\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.