Optimizing the Cutting Stock problem using Column Generation. The data used is taken from CPLEX's example.

0CuttingStockColGen.py

import pulp            #This contains LP Modeling and solver
import time            #This is used to see how much time it takes for solving


#######################################################################
#######################################################################



SizeOfStrips = [25, 40, 50, 55, 70]  #size of strips that can be cut from rolls

DemandOfStrips = [50, 36, 24, 8, 30]   #demand of strips corresponding to the sizes

WidthOfTheRoll = 115   #strips are cut from rolls which have width of 115 units. For example, only 4 25 size strips
                       #can be cut from a roll.

#Objective is to use minimum number of rolls that satisfy the demand of strips. See lp files for better understanding.



#######################################################################
#######################################################################


listOfVariables = list(range(len(SizeOfStrips)))





#------------------------------------------------------------------------------------------------------
# MASTER PROBLEM LP MODELING
#------------------------------------------------------------------------------------------------------




MASCS = pulp.LpProblem("Master Problem Cutting Stock", pulp.LpMinimize)


MDecisionVar = []


for roll in listOfVariables:
    MDecisionVar.append(pulp.LpVariable("roll"+str(roll),0,None,pulp.LpContinuous))


Obj = pulp.LpConstraintVar(name="OBJ",e=sum([MDecisionVar[roll] for roll in listOfVariables]))
MASCS.setObjective(Obj)



Demand = []
for roll in listOfVariables:
    Demand.append(pulp.LpConstraintVar(name="Demand"+str(SizeOfStrips[roll]),
                                       sense=pulp.LpConstraintGE,rhs=DemandOfStrips[roll],
                                       e=int(WidthOfTheRoll/SizeOfStrips[roll]) * MDecisionVar[roll]))
    MASCS += Demand[roll]





#------------------------------------------------------------------------------------------------------
# SUB PROBLEM MIP MODELING
#------------------------------------------------------------------------------------------------------


SUBCS = pulp.LpProblem("Sub Problem Cutting Stock", pulp.LpMinimize)



ConstantCost = pulp.LpVariable("ConstantCost",1,1)
SDecisionVar = pulp.LpVariable.dicts("strip",range(len(SizeOfStrips)),0,None,pulp.LpInteger)  #Binary



SUBCS += pulp.lpSum([int(SizeOfStrips[index]) * SDecisionVar[index] for index in range(len(SizeOfStrips))]) <= WidthOfTheRoll
#constraint knapsack



tic = time.time()




#------------------------------------------------------------------------------------------------------
# COLUMN GENERATION ITERATIONS
#------------------------------------------------------------------------------------------------------



i = 1

while True:

    MASCS.writeLP(str(i)+"MASCS.lp")
    MASCS.solve()
    price = []


    for demand in range(len(DemandOfStrips)):
        price.append(float(MASCS.constraints["Demand"+str(SizeOfStrips[demand])].pi))

    print("Dual values: ",price)
    print()

    SUBCS += sum([ConstantCost-[price[index] * SDecisionVar[index] for index in range(len(SizeOfStrips))]])
    # Objective

    SUBCS.solve()

    SUBCS.writeLP(str(i)+"SUBCS.lp")

    if (pulp.value(SUBCS.objective) >= 0):
        break

    expression = Obj
    for index in range(len(SizeOfStrips)):
        if SDecisionVar[index].value() > 0:
            val = int(SDecisionVar[index].value())
            print("Strip of size:",SizeOfStrips[index]," is cut from the roll ",val,"times.")
            expression += val*Demand[index]


    print()
    print("Master LP problem objective value: ",pulp.value(MASCS.objective))
    print("Subproblem Objective value: ",pulp.value(SUBCS.objective))
    print()

   # print(expression)
   # print()

    MDecisionVar.append(pulp.LpVariable("roll"+str(len(listOfVariables)),0,None,pulp.LpContinuous,e=expression))

    listOfVariables.append(len(listOfVariables))



    print("*************************************************************")
    print("Column Generation Iteration: ",i)
    print()

    i+=1




print("##################*********************######################")
print("****** Column Generation Done. Setting all variables to integers in the Master Problem and solving it... ******")
print()


for variables in MASCS.variables():
    variables.cat = pulp.LpInteger


MASCS.writeLP("MasterInteger.lp")

MASCS.solve()


toc = time.time()


for roll in listOfVariables:
    if MDecisionVar[roll].value() > 0:
        print("Roll",roll,"selected and how many:",MDecisionVar[roll].value())


print("See MasterInteger.lp file to see the roll-strip relationship")

print()
print("Objective value i.e., min. number of rolls needed to satisfy demand:",pulp.value(MASCS.objective))



print("Time taken for solving is " + str((toc-tic)) + " sec")
print()

1MasterProblemSampleLPFile.lp

\* Master Problem Cutting Stock *\
Minimize
OBJ: roll0 + roll1 + roll2 + roll3 + roll4 + roll5
Subject To
Demand25: 4 roll0 >= 50
Demand40: 2 roll1 + roll5 >= 36
Demand50: 2 roll2 >= 24
Demand55: 2 roll3 >= 8
Demand70: roll4 + roll5 >= 30
End

2SubProblemSampleLPFile.lp

\* Sub Problem Cutting Stock *\
Minimize
OBJ: ConstantCost - 0.25 strip_0 - 0.5 strip_1 - 0.5 strip_2 - 0.5 strip_3
 - 0.5 strip_4
Subject To
_C1: 25 strip_0 + 40 strip_1 + 50 strip_2 + 55 strip_3 + 70 strip_4 <= 115
Bounds
ConstantCost = 1
0 <= strip_0
0 <= strip_1
0 <= strip_2
0 <= strip_3
0 <= strip_4
Generals
strip_0
strip_1
strip_2
strip_3
strip_4
End

3FinalMasterProblemIntegerLPfile.lp

\* Master Problem Cutting Stock *\
Minimize
OBJ: roll0 + roll1 + roll2 + roll3 + roll4 + roll5 + roll6 + roll7
Subject To
Demand25: 4 roll0 + roll6 + roll7 >= 50
Demand40: 2 roll1 + roll5 + 2 roll6 + roll7 >= 36
Demand50: 2 roll2 + roll7 >= 24
Demand55: 2 roll3 >= 8
Demand70: roll4 + roll5 >= 30
Bounds
0 <= roll0
0 <= roll1
0 <= roll2
0 <= roll3
0 <= roll4
0 <= roll5
0 <= roll6
0 <= roll7
Generals
roll0
roll1
roll2
roll3
roll4
roll5
roll6
roll7
End