Packing A Small Number Of Packages Into A Fixed Number Of Bins

I have a list of package sizes. There will be a maximum of around 5 different sizes and they may occur a few times (<50). packages = [5,5,5,5,5,5,10,11] I need to pack them int

Solution 1:

Here is a solution using pulp:

from pulp import *

packages = [18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 65, 65, 65]
number_of_bins = 3
bins = range(1, number_of_bins + 1)
items = range(0, len(packages))

x = LpVariable.dicts('x',[(i,b) for i in items for b in bins],0,1,LpBinary)
y = LpVariable('y', 0, 2, LpInteger)
prob=LpProblem("bin_packing",LpMinimize)

#maximize items placed in bins
prob.setObjective(LpAffineExpression([(x[i,b], -3) for i in items for b in bins] + [(y, 1)]))

#every item is placed in at most 1 binfor i in items:
    prob+= lpSum([x[i,b] for b in bins]) <= 1for b in bins:
    if b != 1: # bin 1 is the one with lowest sum
        prob+= LpAffineExpression([(x[i,b], packages[i]) for i in items]  + [(x[i,1], -packages[i]) for i in items])  >= 0if b != number_of_bins: # last bin is the one with highest
        prob+= LpAffineExpression([(x[i,number_of_bins], packages[i]) for i in items]  + [(x[i,b], -packages[i]) for i in items])  >= 0#highest sum - lowest sum <= 2 so every difference of bin sums must be under 2
prob += LpAffineExpression([(x[i,number_of_bins], packages[i]) for i in items]  + [(x[i,1], -packages[i]) for i in items]) <= 2  
prob += LpAffineExpression([(x[i,number_of_bins], packages[i]) for i in items]  + [(x[i,1], -packages[i]) for i in items]) == y

prob.solve()
print(LpStatus[prob.status])

for b in bins:
    print(b,':',', '.join([str(packages[i]) for i in items if value(x[i,b]) !=0 ]))
print('left out: ', ', '.join([str(packages[i]) for i in items ifsum(value(x[i,b]) for b in bins) ==0 ]))

Solution 2:

Tricky one, really not sure about an optimal solution. Below is a solution that just iterates all possible groups and halts at the first solution. This should be a minimal-remainder solution since we first iterate through all solutions without any remainder.

It also iterates over solutions as everything in the first bin, which could be excluded for a faster result.

import numpy as np

defint_to_base_list(x, base, length):
    """ create a list of length length that expresses a base-10 integer
        e.g. binary: int2list(101, 2, 10) returns array([0, 0, 0, 1, 1, 0, 0, 1, 0, 1])
    """
    placeholder = np.array([0] * length)  # will contain the actual answerfor i inreversed(range(length)):
        # standard base mathematics, see http://www.oxfordmathcenter.com/drupal7/node/18
        placeholder[i] = x % base  
        x //= base
    return placeholder

defget_groups(packages, max_diff_sum, number_of_bins):
    """ Get number_of_bins packaging groups that differ no more than max_diff_sum
        e.g. 
        [5, 5, 5, 5, 5, 5, 10, 11] with 2, 3 gives [5,5,5], [10,5], [11,5]
        [5, 10, 12] with 2, 2 gives [10], [12]
        [2, 6, 12] with 2, 3 gives [2], [], []

        We approach the problem by iterating over group indices, so the first
        example above has solution [0 0 0 1 2 3 1 2] with the highest number being
        the 'remainder' group. 
    """
    length = len(packages)
    for i inrange((number_of_bins + 1)**length - 1):  # All possible arrangements in groups 
        index = int_to_base_list(i, number_of_bins + 1, length)  # Get the corresponding indices
        sums_of_bins = [np.sum(packages[index==ii]) for ii inrange(number_of_bins)]
        ifmax(sums_of_bins) - min(sums_of_bins) <= max_diff_sum:  # the actual requirement # print(index)break
    groups = [packages[index==ii] for ii inrange(number_of_bins)] 
    # remainder = packages[index==number_of_bins+1]return groups

On your examples:

packages = np.array([5, 5, 5, 5, 5, 5, 10, 11])
max_diff_sum = 2
number_of_bins = 3
get_groups(packages, max_diff_sum, number_of_bins)

>> [array([5, 5, 5]), array([ 5, 10]), array([ 5, 11])]

And

packages = np.array([5,10,12])
max_diff_sum = 2
number_of_bins = 2
get_groups(packages, max_diff_sum, number_of_bins)

>> [array([10]), array([12])]