Bin packing variant

Question

As in classical bin packing problem, this is an algorithm that optimises the number of bins of a certain size used to hold a list of objects of varying size.

In my variant I also work with a second constraint that is the bins must hold a certain minimum size in them. For example : max_pm = 10, min_pm = 5 ; If we input [8,2,3] then the packing [[8, 2], [3]] is not valid. Some problems also don't hold any solution in which case we should return None.

I implemented this simply as a post-processing solution validation, is there any more optimised way to do it ? I need an optimised solution if it exists, heuristics are not good which is why I've choosed a recursive branching approach.

Items here are size 4 tuples, last value is weight.

from copy import deepcopy

def bin_pack(items, min_pm, max_pm, current_packing=None, solution=None):
    if current_packing is None:
        current_packing = []
    if not items:
        # Stop conditions: we have no item to fit in packages
        if solution is None or len(current_packing) < solution:
            # If our solution doesn't respect min_pm, it's not returned, return best known solution instead
            for pack in current_packing:
                if sum((item[3] for item in pack)) < min_pm:
                    return solution
            # Solutions must be cleanly copied because we pop and append in current_packing
            return deepcopy(current_packing)
        return solution
    # We iterate by poping items and inserting in a list of list of items
    item = items.pop()
    # Try to fit in current packages
    for pack in current_packing:
        if sum((item[3] for item in pack)) + item[3] <= max_pm:
            pack.append(item)
            solution = bin_pack(items, min_pm, max_pm, current_packing, solution)
            pack.remove(item)
    # Try to make a new package
    if solution is None or len(solution) > len(current_packing):
        current_packing.append([item])
        solution = bin_pack(items, min_pm, max_pm, current_packing, solution)
        current_packing.remove([item])
    items.insert(-1, item)
    return solution

Execution example:

print bin_pack([(0,0,0,1), (0,0,0,5), (0,0,0,2), (0,0,0,6)], 3, 6)
# displays [[(0, 0, 0, 6)], [(0, 0, 0, 2), (0, 0, 0, 1)], [(0, 0, 0, 5)]]
print bin_pack([(0,0,0,1), (0,0,0,5), (0,0,0,2), (0,0,0,6)], 4, 6)
# displays None

Answer 1

1. Bugs

1. If any item has weight greater than max_pm, no solution is possible but the code may return a solution anyway. It would be more robust to raise an exception in this case.

2. This condition is wrong:

   len(current_packing) < solution
   

   Here len(current_packing) is an int but solution is a list so in Python 2.7, where you can compare any two values even if they have different types, this always evaluates to True. This can cause the code to return a worse solution when a better solution was discovered earlier. The condition should be:

   len(current_packing) < len(solution)
   

   In Python 3 you couldn't have missed this bug because you would have got an exception:

   TypeError: '<' not supported between instances of 'int' and 'list'
   

2. Review

1. The use of the print statement suggests that you are using Python 2, but this version will no longer be supported from 2020. It would be better to use Python 3. Even if you are stuck on Python 2 for some reason, it would be better to use from __future__ import print_function so that your code can more easily be ported to Python 3 when the time comes.

2. There's no docstring. What does bin_pack do? What arguments does it take? What does it return?

3. Returning None when there is no solution is risky—the caller might forget to check. It is more robust to handle an exceptional case by raising an exception.

4. Some of the names could be improved—since this is a bin packing, the thing being packed ought to be called bin rather than pack. The names min_pm and max_pm are quite obscure: what does pm stand for? Names like min_weight or min_cost or min_size would be clearer.

5. Getting the weight of the items using item[3] is not very flexible—it forces the caller to represent items in a particular way. It would be better for bin_pack to take a function that can be applied to the item to get its weight. Then the caller could pass operator.itemgetter(3).

6. Calling the remove method on a list is not efficient: this method searches along the list to find the first matching item, which takes time proportional to the length of the list. In all the cases where the code uses remove, in fact the item to be removed is the last item in the list and so the pop method could be used instead.

7. It's not clear why the code restores the item at the next-to-last position in the list of items:

   items.insert(-1, item)
   

   Since the item came from the last position in the list, using items.pop(), I would have expected it to be put back at the last position (not the next-to-last) by calling items.append(item).

8. There are some cases where the same information has to be recomputed over and over again: (i) before returning a solution, the code have to check whether all bins have the minimum weight. But this fact could be remembered as part of the current state of the algorithm, so that it doesn't have to be recomputed all the time. (ii) Before deciding whether an item can go into a bin, the code adds up the weights of all the items in the bin. But again, the current weight of each bin could be remembered.

9. Making a deep copy of the solution ends up copying out the contents of the items as well as their organization into the solution. This is unnecessary and possibly harmful—in some use cases the items may not be copyable. A two-level copy is all that's needed here.

10. A bunch of difficulties arise because bin_pack is recursive: (i) passing min_pm and max_pm through all the recursive calls even though these never change; (ii) initializing current_packing on every recursive call even though this ought to only need to be done once; (iii) the best solution has to be pass and returned through all the recursive calls. These difficulties could all be avoided by defining a local function that does the recursion. See below for how you might do this.

11. There is an easy small speedup if you prune branches of the search that can't get you a better solution. See the revised code for how to do this.

3. Revised code

def bin_pack(items, weight, min_weight, max_weight):
    """Pack items (an iterable) into as few bins as possible, subject to
    the constraint that each bin must have total weight between
    min_weight and max_weight inclusive.

    Second argument is a function taking an item and returning its
    weight.

    If there is no packing satisfying the constraints, raise
    ValueError.

    """
    items = [(item, weight(item)) for item in items]
    if any(w > max_weight for _, w in items):
        raise ValueError("No packing satisfying maximum weight constraint")
    bins = []                   # current packing in the search
    bin_weights = []            # total weight of items in each bin
    best = [None, float('inf')] # [best packing so far, number of bins]
    def pack():
        if best[1] <= len(bins):
            return # Prune search here since we can't improve on best.
        if items:
            item, w = item_w = items.pop()
            for i in range(len(bins)):
                bin_weights[i] += w
                if bin_weights[i] <= max_weight:
                    bins[i].append(item)
                    pack()
                    bins[i].pop()
                bin_weights[i] -= w
            if len(bins) + 1 < best[1]:
                bins.append([item])
                bin_weights.append(w)
                pack()
                bin_weights.pop()
                bins.pop()
            items.append(item_w)
        elif all(w >= min_weight for w in bin_weights):
            best[:] = [[bin[:] for bin in bins], len(bins)]
    pack()
    if best[0] is None:
        raise ValueError("No packing satisfying minimum weight constraint")
    return best[0]

Because this needs to run in Python 2.7, I had to make best into a list so that it can be updated from inside the locally defined function pack. In Python 3 we'd have two variables:

best = None
best_bins = float('inf')

and then inside pack we could declare these as nonlocal variables:

nonlocal best, best_bins

and just assign to them like any other variables. But this doesn't work in Python 2.7 because there's no equivalent of the nonlocal statement.