2
$\begingroup$

We have a set of bins that are partitioned into fixed blocks of size $S = \{S_1, S_2, \ldots S_n\}$, and the items are all of sizes from $S$. An item can be allocated to a bin partition if the size of the partition is greater or equal to that item. Our objective is to minimize the number of bins used. Can we have an optimal greedy strategy like sorting the items in non-decreasing order and greedily picking the bin with a matching partition? The scenario that the greedy strategy needs to consider is the notion of multiple choices for the current item to pack since that would impact the subsequent items. Would considering just the nearest item in the future that is different from the current item work? Or would this still be NP Hard?

The bins are similar to the following and this paritioning is fixed. Each item is of one of the parition's size. Note that there can be duplicated sized bins and items.

An image of the bins

$\endgroup$
6
  • $\begingroup$ Would you elaborate more on the first part of your question, specifically, that are partitioned into fixed blocks of size S? $\endgroup$
    – A.Omidi
    Commented Apr 29 at 12:46
  • $\begingroup$ @A.Omidi added a diagram $\endgroup$
    – ephemeral
    Commented Apr 29 at 13:21
  • $\begingroup$ What do you mean by "optimal" in "optimal greedy strategy"? If you are referring to finding the optimal solution, that is possible but certainly not guaranteed. If you mean best possible greedy strategy, that would be hard to prove. $\endgroup$
    – prubin
    Commented Apr 29 at 15:23
  • $\begingroup$ @prubin i mean the optimal solution / an optimal solution that minimizes the number of bins possibly in polynomial time - else possibly a reduction from an NP Hard problem $\endgroup$
    – ephemeral
    Commented Apr 29 at 16:49
  • $\begingroup$ @ephemeral, is it possible to use an LP (not MIP) solver or you have to use an algorithmic manner to solve that? (The idea is, If you can formulate the problem as an LP, you can solve that by any LP solver in a polynomial time to optimality). $\endgroup$
    – A.Omidi
    Commented May 2 at 21:45

2 Answers 2

2
$\begingroup$

Besides the mentioned answer, there are also two possible ways. The first is to suppose each partition with its associated fixed block size as a separate bin. In this way, the problem can be formulated as a bin packing with variable bin size. I am unsure if there exists an algorithm to solve the problem to optimality.

The second approach would be based on the Lagrangian relaxation. Let's define the binary variable $x_{i,s,b}$ if item $i$ is being assigned into the partition $s$ on the bin $b$ equal to one, zero otherwise. The problem can be formulated as:

\begin{array}{l} \text{minimize} \sum_{i,s,b} (s).(ItemSize_{i}).x_{i,s,b}\\ \text{subject to:} \\ \sum_{s,b} x_{i,s,b} = 1 \quad \forall i \quad (1)\\ \sum_{i} x_{i,s,b} \leq |I| \quad \forall s, b \quad (2)\\ \sum_{i,b} ItemSize_{i}.x_{i,s,b} \leq \sum_{m} b_{s,m} \quad \forall s \quad (3)\\ x_{i,s,b} \in\{0,1\} \quad i\in I, \ s \in P, \ b \in B\\ \end{array}

The objective is to minimize the number of bins used. Now, if we omit the third constraint, the problem has the integrality property, Its matrix is TUM, and we can continue with an $LP$. Let's relax the third constraint. The Lagrangian dualized function would be:

\begin{array}{l} \text{Max} \ \mathbb{L}_{(x,\lambda)} = \sum_{i,s,b} (s).(ItemSize_{i}).x_{i,s,b} + \sum_{s} \lambda_{s}*[\sum_{m} b_{s,m} - \sum_{i,b} ItemSize_{i}.x_{i,s,b}] \\ \text{subject to:} \\ (1), (2) \end{array}

By solving the LR dualized function with the aid of an algorithm, like sub-gradient, the problem can be solved to optimality. As far as I remember, the LR dualized function may be solved even without using an LP solver. If I can find/recall that, I will add that.

$\endgroup$
1
$\begingroup$

I do not think that any greedy heuristic can be guaranteed to find an optimal solution. One possible greedy approach is as follows. Sort the items into non-increasing order (largest items first, since they will be the hardest to pack). Put the bins in random order. Assign each item to the first bin with an open slot large enough to handle it, moving partially occupied bins to the front of the list (so that preference is given to adding to a bin in use rather than starting a new bin). You can repeat the heuristic with different random bin orders (only needing to sort the items once).

A possible variant would be to order the bins by something like nondecreasing variance of the slot sizes in the bin, the idea being to encouraging starting bins whose other slots might be big enough to hold subsequent items and would not end up as wasted space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.