Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns) The parameters of the problem are $m$ numbers which are integers (these numbers are denoted $b_i$), $n$ urns and in each urn, we can place $C$ numbers. We assume $nC \geq m$ so that the problem is feasible.
Let's take an example with $m=3$ numbers (with $b_1=1100$, $b_2=540$, $b_3=170$) and $n=2$ urns with capacity $C=4$.
The problem consists to cut the $m$ numbers in order to have $nC$ parts. The cut must preserve each number, for example we have $nC=8$ parts by doing:


*

*$b_1=100+400+450+150$.

*$b_2=100+40+400$.

*$b_3=170$.


Then we must place these $nC$ numbers in the urns (knowing that each urn has a capacity of $C=4$), for example:


*

*Urn 1: $40$ (2) - $170$ (3) - $100$ (2) - $450$ (1)

*Urn 2: $100$ (1) - $150$ (1) - $400$ (2) - $400$ (1)


The cost $f$ of any solution is defined as the sum of the biggest numbers in each urn, in this case: $f=450+400=850$.
The goal of the problem is to decide how to cut the numbers and how to gather them in the urns in order to minimize the cost (actually, I have no idea what is the optimal solution of the previous instance).
I am not looking for an algorithm to solve this problem but I am wondering if this problem is NP-hard. Maybe this problem can be linked with another combinatorial optimization problem ?
I already searched and all that I could find is that the problem is easy if $n=1$ (and we still assume $C \geq m$) and that there is a polynomial algorithm in that case.
Thank you very much!
 A: Edit Using 3-PARTITION instead of PARTITION in the reduction below, we get that the problem is strongly NP-hard.
I think we get NP-hardness by the following reduction from PARTITION. Let a PARTITION instance be given by positive integers $a_1,\ldots,a_N$ with $a_1+\cdots+a_N=2B$ where the question is if we can select an index set $I\subseteq\{1,\ldots,N\}$ with $\sum_{i\in I}a_i=B$. We define an instance of the spaghetti cutting problem with the following data


*

*number of jars: $n=N$

*jar capacity: $C=N+2$

*number of spaghetti pieces: $m=N(N+1)+2$

*spaghetti lengths: For each $i\in\{1,\ldots,N\}$, there are $N+1$ pieces of length $a_i$, and in addition there are 2 pieces of length $B$.


The trivial lower bound for this instance is $(\sum_{i=1}^mb_i)/C=2B$, and I claim that it can be achieved if and only if the PARTITION instance is a YES-instance. The "if"-part is obvious: You can cut the two pieces of length $B$ into $N$ pieces with lengths $a_1,\ldots,a_N$, and then we have one jar full of length $a_i$ pieces for every $i$. For the "only if" part it helps to assume $a_1>a_2>\cdots>a_N$ which is no problem (see here). In order to achieve the objective value $2B$ we need one jar full of pieces of length $a_1$, so we have to cut a piece of length $a_1$ from one of the two long spaghetti pieces. Then we can assume w.l.o.g. that we don't cut the pieces of length $a_1$. Next we need a jar full of pieces of length $a_2$, which can be achieved only by cutting it from one of the long pieces. Continuing in this way we complete the argument.
This leaves open what happens for bounded capacity $C$. The first interesting case is $C=2$, for which the question if the lower bound $(\sum_{i=1}^mb_i)/2$ is achievable can be formulated as follows: Given $b_1,\ldots,b_m$ and $n> m/2$, can we cut the $b_i$'s into $2n$ pieces such that every length appears an even number of times?
For what it's worth, here is a mixed binary programming formulation for the general problem:
\begin{align*}
\text{Minimize }\sum_{j=1}^n&x_{(j-1)C+1}\qquad\text{subject to}\\
x_1\geqslant &x_2\geqslant\cdots\geqslant x_{nC},\\
\sum_{k=1}^{nC}y_{ik} &= b_i &&i\in[m],\\
\sum_{i=1}^my_{ik} &= x_k && k\in[nC],\\
y_{ik} &\leqslant b_iz_{ik} && i\in[m],\ k\in[nC],\\
\sum_{i=1}^mz_{ik} &\leqslant 1 &&k\in[nC],\\
y_{ik} &\geqslant 0,\ z_{ik}\in\{0,1\} && i\in[m],\ k\in[nC].
\end{align*}
