2
$\begingroup$

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?

  • 0
    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.2011-01-14
  • 1
    Have you thought about looking into lattice reduction algorithms (i.e. [LLL](http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm) or [PSLQ](http://mathworld.wolfram.com/PSLQAlgorithm.html))? I believe they've had some success with problems similar to this (googling found [this](http://www.math.ucsd.edu/~crypto/Projects/JenniferBakker/Math187/index.html), though I don't know how useful it will be).2011-01-14
  • 0
    @user4143: Would you add that as an answer?2011-01-21

1 Answers 1

2

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.

  • 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.2011-01-14
  • 1
    By the way, the S_i cannot be disjoint (for t > 1) since S_t = S contains all the weights.2011-01-14
  • 0
    Why would you have $S_t$? I though you have $S_1, \dots S_k$. Anyway, please consider my (not very fruitful) edit.2011-01-14
  • 0
    That's the greedy algorithm -- reasonable, though certainly not optimal.2011-01-15