Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'd like a good way to solve an optimization problem I came across. It's a constrained knapsack problem: I want to find integers

$$1=a_1\le a_2\le\cdots\le a_t$$

$$a_1+a_2+\cdots+a_t=N$$

with $t$ as small as possible such that (with the $S_i\subseteq S={a_1,a_2,\ldots,a_t}$)

$$\sum_{e\in S_i}e=C_i$$

for a certain fixed collection $C_1 = 1, C_2 = 4,\ldots,C_k=N.$

What software exists for this sort of problem? I feel like writing my own program from the ground up would be the wrong approach.

I've been toying with COIN-OR and such but they seem set up for very different sorts of problems.


Ideally, I'd solve an even more complicated problem where $C_1$ and $C_k$ must match exactly and the other sums must be within a fixed range depending on the values of the neighboring C-values... but I don't imagine this is feasible?

share|improve this question
    
For an idea of the size of the problem, t = 10 is almost certainly infeasible and t = 250 is feasible. k = 255 and N is around 50,000. A good solution would be fine -- I don't need to find the best possible. –  Charles Jan 14 '11 at 15:54
1  
Have you thought about looking into lattice reduction algorithms (i.e. LLL or PSLQ)? I believe they've had some success with problems similar to this (googling found this, though I don't know how useful it will be). –  user4143 Jan 14 '11 at 20:10
    
@user4143: Would you add that as an answer? –  Charles Jan 21 '11 at 16:43
add comment

1 Answer

up vote 2 down vote accepted

This is not a variation of KNAPSACK since you can choose your weights.

From what you write, I assume that $C_1 < C_2 < \dots C_k$. Let me also explicitly state that you never demand the $S_i$ to be disjoint; the following approach would not work then.

Note first that you can safely drop the first restriction $1 = a_1 \leq \dots$. If you find feasible $a_i$ in any order, this can always be achieved by renaming.

Edit: The offered solution is suboptimal as has been pointed out in the comments.

Let $a_1 = 1$ and for $2 \leq i \leq k$ let $a_i = C_i - C_{i-1}$. These $a_i$ are an optimal solution since

  • $C_i = \sum_{j=1}^i a_j$ obviously and
  • $t=k$ is the minimum $t$ possible. Since all $C_i$ are pairwise different, we need at least one summand per $C_i$.

Edit: A new idea.

Start with $A = \{N\}$. For every $i$ from $N-1$ to $1$ do:

  • If you can sum up $C_i$ with what is in $A$, continue with $i-1$.
  • Let $m = \min \{ a \in A \mid a \geq C_i\}$
  • If $m \neq C_i$, choose $p = \arg\min_r \{ |q - r| \mid r+q=m, r+a=C_i, a\in A_{< C_i}\cup\{0\} \}$ and set $A = (A \setminus \{m\}) \cup \{p, m-p\}$

The rather ugly argmin in words: For every $C_i$ take the smallest already chosen summand larger than $C_i$ and break it in as big chunks as possible while making sure that you can build $C_i$ with what you have. That should always work out, i.e. yield a solution.

I have no idea regarding optimality. For your example, the solution provided by you is found. Of course, I use SUBSET SUM, what is probably a bad idea. Doh.

share|improve this answer
2  
That's not optimal. Suppose the C are (1, 2, 3, 4, 5, 6, 7, 28). Your solution gives (1, 1, 1, 1, 1, 1, 1, 21), a total of 8 members. But (1, 2, 4, 21) also works and is much smaller. –  Charles Jan 14 '11 at 19:59
1  
By the way, the S_i cannot be disjoint (for t > 1) since S_t = S contains all the weights. –  Charles Jan 14 '11 at 20:00
    
Why would you have $S_t$? I though you have $S_1, \dots S_k$. Anyway, please consider my (not very fruitful) edit. –  Raphael Jan 14 '11 at 23:57
    
That's the greedy algorithm -- reasonable, though certainly not optimal. –  Charles Jan 15 '11 at 19:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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