Allocating production jobs for films for multiple film manufacturing machines with PuLP (python)

Question

I am trying to solve a problem which is somewhat similar to the bin packing problem. In this problem I have to assign jobs to film manufacturing machines where the machines have different film widths. All the machines must have the same amount of useage. Each roll has a specific width. Multiple jobs can be completed by the machine was long as the sum of all the job widths are less than the machine film width.

I have modeled it as a bin packing problem. Because I needed to make sure that all the machines have the same number of rolls I have the bins as a 2-d array where each type has multiple bins. In my formuation c is the capacity of the machine, x is a binary variable which specifies if a bin is being used, y is a binary variable which specifies if a roll is assigned to a bin. The overall objective is to minimize the waste generated.

Based on this, I wrote python code using pulp

from pulp import *
prob = LpProblem("Production Problem",LpMinimize)
capacity = [1350, 2100]
rolls = [970, 1050, 970, 1100, 1050, 500, 500, 500, 1050, 1350,1200, 370]
I = range(2) # machine film width
J = range(10) # bins for each machine film width 
K = range(len(rolls)) # number of rolls in total 

# variable to determine wether a particular bin is used
x = LpVariable.dicts(name = "Bin", indexs = ((i,j) for i in I for j in J), cat = 'Binary')
# variable to determine if roll is assigned to a particular bin 
y = LpVariable.dicts(name = "RollBin", indexs = ((i,j, k) for i in I for j in J for k in K), cat = 'Binary')
# variable to calculate wastage 
w = LpVariable(name = 'wastage', lowBound = 0, cat = LpInteger)

w = LpVariable(name = 'wastage')
for j in J:
    for i in I:
        firstPart = capacity[i] * x[(i,j)]
        for k in K:
            secondPart = rolls[k] * y[(i,j,k)]
        w += firstPart - secondPart
prob+=w

#each roll is assigned to exactly 1 bin
for k in K:
    prob += lpSum([y[(i,j,k)] for i in I for j in J]) == 1

#bin size is not exceeded
for i in I:
    for j in J:
        prob += lpSum(rolls[k] * y[(i,j,k)] for k in K) - capacity[i] * x[(i,j)] <= 0

# similar number of bins of each type are used 
# for i in range(0,len(capacity)-1):
#         prob+= lpSum(x[(i,j)] for j in J) - lpSum(x[(i + 1,j)] for j in J) <= 2
prob+= x[(i,j)] == x[i+1,j] for i in I for j in J 

status = prob.solve()
print(prob)
for v in prob.variables():
    if v.varValue > 0:
        print(v.name, "=", v.varValue)
print(value(prob.objective))
print(LpStatus[status])

My first problem is that I am not sure how to specify the last constraint. Right now it throws an error. Secondly, I tried removing the constraint and got an objective value of 0 which is definitely wrong. I thought that the first constraint would ensure that all the rolls would be assigned to a machine but when I printed out the solution, none of the rolls were assigned and none of the machines(bins) were being used.

Can someone please help me out here. Is there something wrong with my formuation?

[Update]: Only the original question is included now.

Answer 1

My first problem is that I am not sure how to specify the last constraint. Right now it throws an error.

Constraint in correct format:

for i in I[:-1]:
    for j in J:
        prob += x[i,j] == x[i+1,j]

Secondly, I tried removing the constraint and got an objective value of 0 which is definitely wrong. I thought that the first constraint would ensure that all the rolls would be assigned to a machine but when I printed out the solution, none of the rolls were assigned and none of the machines(bins) were being used.

There are some other minor issues.

In this block:

w = LpVariable(name = 'wastage')
for j in J:
    for i in I:
        firstPart = capacity[i] * x[(i,j)]
        for k in K:
            secondPart = rolls[k] * y[(i,j,k)]
        w += firstPart - secondPart
prob+=w

secondPart is updated all the time, and it ends up taking the value of the last k only. You probably don't want this. Also, my understanding is that the expression w+= adds terms to the objective function. However, prob+=w adds w on top of the other terms that have been added, and since w is a continuous unbounded variable, the problem is unbounded. I added a lower bound of zero at w and it worked OK.

Correct block:

w = LpVariable(name = 'wastage', lowBound=0)
for j in J:
    for i in I:
        firstPart = capacity[i] * x[(i,j)]
        secondPart = lpSum(rolls[k] * y[(i,j,k)] for k in K)
        w += firstPart - secondPart
prob+=w

All code amended (I removed the solver because I do not have it):

from pulp import *
prob = LpProblem("Production Problem",LpMinimize)
capacity = [1350, 2100]
rolls = [970, 1050, 970, 1100, 1050, 500, 500, 500, 1050, 1350,1200, 370, 370]

I = range(2) # machine film width
J = range(10) # bins for each machine film width 
K = range(len(rolls)) # number of rolls in total 

# variable to determine wether a particular bin is used
x = LpVariable.dicts(name = "Bin", indexs = ((i,j) for i in I for j in J), lowBound = 0, upBound = 1, cat = 'Integer')
# variable to determine if roll is assigned to a particular bin 
y = LpVariable.dicts(name = "RollBin", indexs = ((i,j, k) for i in I for j in J for k in K), lowBound = 0, upBound = 1, cat = 'Integer')
w = LpVariable(name = 'wastage', lowBound=0)
for j in J:
    for i in I:
        firstPart = capacity[i] * x[(i,j)]
        secondPart = lpSum(rolls[k] * y[(i,j,k)] for k in K)
        w += firstPart - secondPart
prob+=w
#prob += lpSum(capacity[i] * x[(i,j)] - lpSum(rolls[k]*y[(i,j,k)] for k in K) for i in I for j in J)

for k in K:
    prob += lpSum([y[(i,j,k)] for i in I for j in J]) == 1

for k in K:
    prob += lpSum([rolls[k] * y[(i,j,k)] for i in I for j in J]) <= lpSum([capacity[i] * x[(i,j)] for i in I for j in J])

for i in I[:-1]:
    for j in J:
        prob += x[i,j] == x[i+1,j]

status = prob.solve()
print(prob)
for v in prob.variables():
    if v.varValue > 0:
        print(v.name, "=", v.varValue)
print(value(prob.objective))
print(LpStatus[status])

Solution output:

('Bin_(0,_9)', '=', 1.0)
('Bin_(1,_9)', '=', 1.0)
('RollBin_(0,_3,_7)', '=', 1.0)
('RollBin_(0,_4,_12)', '=', 1.0)
('RollBin_(0,_6,_5)', '=', 1.0)
('RollBin_(0,_7,_10)', '=', 1.0)
('RollBin_(1,_0,_2)', '=', 1.0)
('RollBin_(1,_0,_6)', '=', 1.0)
('RollBin_(1,_2,_0)', '=', 1.0)
('RollBin_(1,_3,_11)', '=', 1.0)
('RollBin_(1,_4,_3)', '=', 1.0)
('RollBin_(1,_6,_1)', '=', 1.0)
('RollBin_(1,_8,_4)', '=', 1.0)
('RollBin_(1,_9,_8)', '=', 1.0)
('RollBin_(1,_9,_9)', '=', 1.0)
-7530.0
Optimal

Note also that Erwin's comment is true: x_{ij} is over-engineered. I did not touch on this, but it is indeed a good idea to give a single index to x.

I hope this helps!