Two Dimensional Bin Packing

Question

I am using the following Integer Programming Model for solving the Two Dimensional Bin Packing Problem. The following model illustrates the one dimensional version. The code I have written incorporates the constraints for the additional dimension.

---

I am using Python PuLP for solving the optimization problem. The code is as follows :

from pulp import *

#knapsack problem

def knapsolve(item):

    prob = LpProblem('BinPacking', LpMinimize)

    ys = [LpVariable("y{0}".format(i+1), cat="Binary") for i in range(item.bins)]

    xs = [LpVariable("x{0}{1}".format(i+1, j+1), cat="Binary")
          for i in range(item.items) for j in range(item.bins)]

    #minimize objective
    nbins = sum(ys)
    prob += nbins

    print(nbins)

    #constraints

    t = nbins >= 1
    print(t)
    prob += t

    for i in range(item.items):
        con1 = sum(xs[(i + j*item.bins)] for j in range(item.bins))
        t = con1 == 1
        prob += t
        print(t)

    for k in range(item.bins):
        x = xs[k*item.bins : (k+1)*item.bins]
        con1 = sum([x1*w for x1, w in zip(x, item.itemweight)])
        t = con1 <= item.binweight[k] * ys[k]
        #t = con1 <= item.binweight[k]
        prob += t
        print(t)

    for k in range(item.bins):
        x = xs[k*item.bins : (k+1)*item.bins]
        con1 = sum([x1*w for x1, w in zip(x, item.itemheight)])
        t = con1 <= item.binheight[k] * ys[k]
        #t = con1 <= item.binheight[k]
        prob += t
        print(t)

    status = prob.solve()

    print(LpStatus[status])
    print("Objective value:", value(prob.objective))
    print ('\nThe values of the variables : \n')

    for v in prob.variables():
        print(v.name, "=", v.varValue)

    return

class Item:
    #bins, binweight, items, weight, itemheight, binheight

    bins = 5
    items = 5

    binweight = [2,3,2,5,3]
    itemweight = [1,2,2,1,3]

    itemheight = [2,1,4,5,3]
    binheight = [4,9,10,8,10]


item = Item()

knapsolve(item)

It produces the following output :

y1 + y2 + y3 + y4 + y5
y1 + y2 + y3 + y4 + y5 >= 1
x11 + x21 + x31 + x41 + x51 = 1
x12 + x22 + x32 + x42 + x52 = 1
x13 + x23 + x33 + x43 + x53 = 1
x14 + x24 + x34 + x44 + x54 = 1
x15 + x25 + x35 + x45 + x55 = 1
x11 + 2*x12 + 2*x13 + x14 + 3*x15 - 2*y1 <= 0
x21 + 2*x22 + 2*x23 + x24 + 3*x25 - 3*y2 <= 0
x31 + 2*x32 + 2*x33 + x34 + 3*x35 - 2*y3 <= 0
x41 + 2*x42 + 2*x43 + x44 + 3*x45 - 5*y4 <= 0
x51 + 2*x52 + 2*x53 + x54 + 3*x55 - 3*y5 <= 0
2*x11 + x12 + 4*x13 + 5*x14 + 3*x15 - 4*y1 <= 0
2*x21 + x22 + 4*x23 + 5*x24 + 3*x25 - 9*y2 <= 0
2*x31 + x32 + 4*x33 + 5*x34 + 3*x35 - 10*y3 <= 0
2*x41 + x42 + 4*x43 + 5*x44 + 3*x45 - 8*y4 <= 0
2*x51 + x52 + 4*x53 + 5*x54 + 3*x55 - 10*y5 <= 0
Optimal
Objective value: 3.0

The values of the variables : 

x11 = 0.0
x12 = 0.0
x13 = 0.0
x14 = 0.0
x15 = 0.0
x21 = 0.0
x22 = 0.0
x23 = 1.0
x24 = 0.0
x25 = 0.0
x31 = 0.0
x32 = 0.0
x33 = 0.0
x34 = 0.0
x35 = 0.0
x41 = 0.0
x42 = 1.0
x43 = 0.0
x44 = 0.0
x45 = 1.0
x51 = 1.0
x52 = 0.0
x53 = 0.0
x54 = 1.0
x55 = 0.0
y1 = 0.0
y2 = 1.0
y3 = 0.0
y4 = 1.0
y5 = 1.0

The sample input data that has been hard coded, should produce 1 bin as the output, that is one y variable should have the value 1. However this is not the case. Are the equations modeled properly? Is there another way to specify the constraints?

Answer 1

The mathematical model for the standard bin-packing problem uses x(bins,items) while in the Python model you seem to use a mix of of x(bins,items) and x(items,bins). The assignment to xs uses x(items,bins) but the construct xs[(i + j*item.bins)] implies x(bins,items). This is easily seen by inspecting the output: x11 + x21 + x31 + x41 + x51 = 1 which indicates x(bins,items). This type of modeling with explicit index calculations is rather unreliable in practice. This is a toy model, but for real models the lack of type checking can be very dangerous.

Different bin weights and heights should be no problem.

Also given your data

binweight = [2,3,2,5,3]
itemweight = [1,2,2,1,3]   
itemheight = [2,1,4,5,3]
binheight = [4,9,10,8,10]

I don't believe this can be handled by just 1 bin as you claim. You need 3 bins for this (bins 2,4 and 5). (You are lucky here because although there are actually bugs in the Python code you get good solutions).