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 empty boxes in the van. Also, the value of each object doesn't depend on itself but on the box you save it. The problem is maximizing the transported value while respecting all of the above restrictions. Ah... almost forgot, the weights are multidimensional.

Formally, given the following entities, where all vectors are column vectors, each element of every vector/matrix is a natural number $\geq 0$, and all weights are $q$-dimensional vectors:

  1. $W$: the weight of the moving van.
  2. $n$ and $m$: the amount of available objects and boxes respectively.
  3. $V$: a $n\times m$ matrix where each element is the value of saving each object in each box.
  4. $w_o$: a $n$-dimensional vector with the weights of each object.
  5. $w_B$: a $m$-dimensional vector with the weights of each box.
  6. $l$ and $u$: two $m$-dimensional vectors that, together, forms the size limits of each box (lower and upper bounds per box respectively).

The problem consists of finding:

  1. $X$: a $n\times m$ matrix with the amount of times each object has been choosen to be saved in each box, and
  2. $y$: a $m$-dimensional vector with the amount of times each box has been choosen,

in order to achieve: $$ \begin{align} \max\quad & \sum_{i=1}^n\sum_{j=1}^mv_{ij}x_{ij}\\ \text{s.t.}\quad & w_B\cdot y + w_o\cdot\texttt{columnsum(X)}\leq W\\ &y\cdot l\leq \texttt{rowsum(X)}\leq y\cdot u\\ &X\geq 0\\ &y\geq 0 \end{align} $$

where $\texttt{columnsum}(X)$ is a vector with how many times each object has been choosen in total (sum of columns), and $\texttt{rowsum}(X)$ is a (column) vector with how many objects have been saved in each box in total (sum of rows and then transposed).

I want to know if there's any formal name for this problem, to search algorithms for it in the bibliography. What I have tried is to see it as an instance of an integer programming problem, but I'm not able to adapt its mathematical formulation to match the canonical form of ILPs, so I don't know if I'm in the right path or have to look somewhere else.

  • $\begingroup$ Presumably you can express it as an integer linear programming instance but not a linear programming instance. I'm not sure whether that's what you are asking. $\endgroup$ – D.W. Jan 6 at 19:29
  • $\begingroup$ @D.W. The problem is that I don't know how to reformulate the problem in canonical form, or whether that is even possible. $\endgroup$ – Peregring-lk Jan 6 at 19:39
  • $\begingroup$ I'm not sure what you mean by "canonical form". There are often multiple ways to formulate a problem mathematically. I also don't see any mention of that in the question. $\endgroup$ – D.W. Jan 6 at 19:40
  • $\begingroup$ @D.W. I mean making my problem have this form: en.wikipedia.org/wiki/Simplex_algorithm#Overview $\endgroup$ – Peregring-lk Jan 6 at 23:08
  • $\begingroup$ @D.W. I have edited the last paragraph of my question. I hope it's a bit clearer now. $\endgroup$ – Peregring-lk Jan 6 at 23:21

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.