1CC2000 - Algorithmique et Complexité - TD06 Practice

TD06 - Bin Packing

Implementation in Python 3 of a greedy algorithm to approximate the Bin Packing problem as seen in TD 7.

Each code you need to complete is followed by tests to verify that the data produced when the function was called is correct.

Exercise plan :

Bin Packing is {$\mathcal{NP}$} ;
First-Fit algorithm ;

Optional :

Best-Fit algorithm.

Bin packing instances are loaded in the first cell. They will help to test the produced algorithms.

# TO RUN 
def big_instance():
    bi = [99, 99, 97, 97, 97, 97, 97, 96, 96, 96, 96, 96, 96, 94, 94, 94, 93, 92, 92, 89, 89, 89, 88, 88, 87, 87, 86, 85, 85, 85, 84, 84, 84, 83, 83, 83, 83, 83, 83, 82, 81, 81, 81, 80, 80, 80, 79, 79, 79, 78, 78, 77, 76, 76, 75, 74, 73, 72, 71, 71, 71, 71, 69, 69, 68, 68, 68, 68, 67, 67, 66, 66, 66, 65, 65, 65, 65, 65, 64, 64, 64, 63, 63, 60, 60, 58, 58, 58, 58, 57, 57, 57, 56, 56, 56, 55, 54, 54, 53, 53, 53, 53, 52, 52, 50, 50, 49, 49, 47, 46, 45, 45, 45, 44, 44, 43, 42, 42, 41, 41, 41, 41, 40, 40, 40, 40, 40, 40, 39, 39, 38, 38, 38, 37, 37, 37, 37, 36, 36, 35, 34, 34, 34, 34, 34, 33, 33, 32, 32, 31, 31, 31, 30, 30, 29, 28, 27, 27, 27, 26, 25, 25, 24, 23, 22, 22, 21, 21, 21, 21, 20, 19, 19, 19, 18, 17, 17, 17, 16, 15, 13, 13, 13, 10, 10, 9, 9, 9, 9, 9, 9, 8, 7, 6, 6, 5, 4, 3, 2, 1]
    return bi, 120

# The TD example
# inputs 
O = [4, 4, 5, 5, 5, 4, 4, 6, 6, 2, 2, 3, 3, 7, 7, 2, 2, 5, 5, 8, 8, 4, 4, 5] # objects
B = 10 # bin size
# optimal solution in 11 bins :
L = [[8, 2], [8, 2], [7, 3], [7, 3], [6, 4], [6, 4], [5, 5], [5, 5], [5, 5], [4, 4, 2], [4, 4, 2]]

Bin Packing is {$\mathcal{NP}$}

Complete the boolean function verifyBP(O, B, k, L) that takes as parameters:

O the list of objects sizes,
B the size of a bin,
k a maximum number of bins to use. O, B and k are the inputs of the problem.
L the solution to verify. L is a list of sublists of O (corresponding to bins) that form a partition of O (see the TD example in the cell above).

It verifies that :

{$size(L) \leq k$} : at most {$k$} bins;
{$\bigcup_i L_i = O$} : {$L$} is a partition of {$O$};
{$\forall~i.~sum(L_i) \leq B$} : It fits to bins, we suppose {$\forall o \in O, o \leq B$}.

def verifyBP(O, B, k, L):
    ############### TODO : complete code ##################### 


    return True

To verify that your function is working properly, we will perform a set of tests, run the following cell:

import random

OO, LL = O[:], L[:]

random.shuffle(LL) # shake!

assert     verifyBP(OO,      B, len(OO),   [[o] for o in OO] )
assert not verifyBP(OO,      B, len(OO)-1, [[o] for o in OO] ) 
assert     verifyBP(OO,      B, len(LL)  , LL                ) 
assert     verifyBP(OO,      B, len(LL)+1, LL                ) 
assert not verifyBP(OO,      B, len(LL)-1, LL                ) 

assert not verifyBP(OO,      B, len(LL),   LL[1:]            ) 
assert not verifyBP(OO,      B, len(LL)+1, LL+[LL[0]]         ) 
assert     verifyBP(OO+LL[0], B, len(LL)+1, LL+[LL[0]]         ) 
assert     verifyBP(OO,      B, len(LL),   LL[1:]+[LL[0]]     ) 
assert not verifyBP(OO,      B, len(LL),   [LL[0]+LL[1]]+LL[2:]) 

print("OK! you passed these tests (still not a proof)")

Greedy algorithm : First-Fit

Propose a greedy algorithm to solve/approximate the Bin Packing problem using the First-Fit heuristic placing each object into the first bin in which it will fit.

Complete the function first_fit(O, B) that takes as parameters the list of objects sizes O and the size of bins B and then returns a solution L of the form detailed above.

def first_fit(O, B):
    L = []
    ############### TODO : complete code #####################     for o in O:


    return L

# Tests
L_FF = first_fit(O, B)
assert len(L_FF) == 13
print(len(L_FF), "bins:", L_FF) # >>> 13 bins: ...

What if we sort objects in descending order?

L_FFD = first_fit(sorted(O,reverse = True), B)
print(len(L_FFD), "bins:", L_FFD) # >>> 11 bins: ... 
if len(L_FFD) == round(sum(O)/B):
    print("OPTIMAL!!") # >>> OPTIMAL!!

Let's load a bigger instance with 200 objects of sizes from 1 to 100. The bins are of size 120 and the optimal solution uses 88 bins (see the best-fit result).

OO, BB = big_instance() # OO is already sorted in descending order
LL = first_fit(OO,BB)
assert len(LL) == 89 # >>> 89 bins # NOT OPTIMAL!!

[Optional] Greedy algorithm : Best-Fit

Propose a greedy algorithm to solve/approximate the Bin Packing problem using the Best-Fit heuristic placing each object into the bin of the minimum empty space in which it will fit.

Complete the function best_fit(O, B) that takes as parameters the list of objects sizes O and the size of bins B and then returns a solution L of the form detailed above.

def best_fit(O, B):
    L = []
    ############### TODO : complete code ##################### 


    return L

# Tests
L_BF = best_fit(O, B)
print(len(L_BF), "bins:", L_BF) # >>> 12 bins: ...
assert len(L_BF) == 12

# what if we sort objects in descending order?
L_BFD = best_fit(sorted(O,reverse = True), B)
print(len(L_BFD), "bins:", L_BFD) # >>> 11 bins: ... # OPTIMAL!!
assert len(L_BFD) == sum(O)//B

Back to the bigger instance, do we obtain the optimal solution, do we do better?

LL = best_fit(OO,BB)
assert len(LL) == round(sum(OO)/BB) # >>> OPTIMAL!!