My problem is related to the standard bin packing problem, but in my case each item has a value, and the objective is to minimise the number of bins used to pack all the items PLUS the sum of the maximum value in each bucket.

Formally, given a bin $S$ of size $V$ and a list of $n$ items with sizes $a_1,\dots,a_n$ and values $v_1,\dots,v_n$ to pack, find an integer number of bins $B$ and a $B$-Partition of a set $S_1 \cup \dots \cup S_B$ of the set $\{1,\dots,n\}$ such that $\sum_{i \in S_k} a_i \leq V$ for all $k=1,\dots,B$. Such partition shoud be the one that minimises the quantity $B+\sum max_{i\in S_k}v_i$ for all $k=1,\dots,B$.

Do you know if this particular version has been studied before and if it has a good approximate solution algorithm?

  • 1
    $\begingroup$ Can you state a bit more formally/specifically what your objective is? I don't quite understand it as currently written... $\endgroup$ – usul Jun 20 '14 at 23:33
  • $\begingroup$ I've modified the original question with a formal explanation $\endgroup$ – Filippo Bistaffa Jun 21 '14 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.