This problem is a mix of the bin-packing and the knapsack problems. I call it “the moving van problem”: there is a moving van with a limit on the weight it can transport, and a set of boxes that you want to fill with valuable objects to be transported in the van. Both the boxes and the objects that are available can be choosen repeatedly and have weights. Also, the size of each box is bounded by above and below (their size limits), so you cannot put, for example, empty boxes in the van.
More:
- not all boxes accept all objects: the available objects and boxes are partitioned so that any object of a group can be saved in any box of the same group, but nowhere else;
- also, the value of each object doesn’t depend on itself but on the box you save it;
- lastly, the box size limit of all boxes of a same group are the same.
The problem is maximizing the transported value while respecting all of the above restrictions. Ah… almost forgot, the weights are multidimensional.
Formally:
- I have one $m$-dimensional van whose capacity is $overline{W}=(W_1, …, W_m)$.
- I have $n$ groups where each group $G_i={B_i, O_i, V_i, l_i, u_i}$:
- Each $overline{b_{ij}}in B_i$ is the $m$-dimensional weight of the $j$-th box, and each $overline{o_{ik}}in O_i$ is the $m$-dimensional weight of the $k$-th object.
- $V_i$ is a matrix of size $|B_i|times|O_i|$, where $v_{ijk}$ is the value given by the $j$-th box to the $k$-th object.
- $l_i$ and $u_i$ are the box size limits that applies to every box of the group, and satisfy $1leq l_ileq u_i$.
- Let’s call $x_{ij}$ the number of times the $j$-th box has been choosen.
- Let’s call $x_{ijk}$ the total number of times the $k$-th object has been saved in $j$-th boxes.
- Let’s call $f_{ij} =sum_{k=1}^{|O_i|}x_{ijk}$, the total number of items saved in $j$-th boxes, or its filled size.
- The problem is then: $$
begin{align}
maxquad & sum_{i=1}^nsum_{j=1}^{|B_i|}sum_{k=1}^{|O_i|}v_{ijk}x_{ijk}\
text{s.t.}quad & sum_{i=1}^nsum_{j=1}^{|B_i|}left(overline{b_{ij}}x_{ij}+sum_{k=1}^{|O_i|}overline{o_{ik}}x_{ijk}right)leq overline{W}\
& forall i,~forall jleq|B_i|~:~l_ileq frac{f_{ij}}{x_{ij}}leq u_i\
end{align}
$$
The question is, is there any formal problem with a similar formulation, or some way of transforming this problem to some other famous problem? Of course, my ultimate question is an efficient algorithm for this. I guess this problem is NP-hard because it’s almost an NP-hard problem inside another one.
Fortunately, my instances are not big so I’m even interested in exact algorithms to see if they behave well for me.
I have tried to vectorized a bit more the formulation of the problem and replace inner $sum$ by dot products, trying to see any pattern or resemblance with other knapsack problems, but those vectorizations attempts were confusing me even more and running me out of symbols to name things.
