0
$\begingroup$

I have implemented the following Column Generation model in Gurobi. Unfortunately, I currently have the problem that the constraint in the master problem is not linear and therefore I cannot add the column by default. I have tried to linearize the constraint, but unfortunately I can't get it to be considered in the Column() object. This is error i get:

NameError: name 'newcon' is not defined

I know that the newcon doesn't gets passed, but how would I need to modify my code in order to accomplish a successful "passing"?

And this is my code:

from gurobipy import *
import gurobipy as gu
import pandas as pd
import itertools
import time
import matplotlib.pyplot as plt

# Create DF out of Sets
I_list = [1, 2, 3]
T_list = [1, 2, 3, 4, 5, 6, 7]
K_list = [1, 2, 3]
I_list1 = pd.DataFrame(I_list, columns=['I'])
T_list1 = pd.DataFrame(T_list, columns=['T'])
K_list1 = pd.DataFrame(K_list, columns=['K'])
DataDF = pd.concat([I_list1, T_list1, K_list1], axis=1)
Demand_Dict = {(1, 1): 2, (1, 2): 1, (1, 3): 0, (2, 1): 1, (2, 2): 2, (2, 3): 0, (3, 1): 1, (3, 2): 1, (3, 3): 1,
               (4, 1): 1, (4, 2): 2, (4, 3): 0, (5, 1): 2, (5, 2): 0, (5, 3): 1, (6, 1): 1, (6, 2): 1, (6, 3): 1,
               (7, 1): 0, (7, 2): 3, (7, 3): 0}


class MasterProblem:
    def __init__(self, dfData, DemandDF, iteration):
        self.iteration = iteration
        self.physicians = dfData['I'].dropna().astype(int).unique().tolist()
        self.days = dfData['T'].dropna().astype(int).unique().tolist()
        self.shifts = dfData['K'].dropna().astype(int).unique().tolist()
        self.roster = list(range(1, self.iteration + 2))
        self.demand = DemandDF
        self.model = gu.Model("MasterProblem")
        self.cons_demand = {}
        self.newvar = {}
        self.cons_lmbda = {}

    def buildModel(self):
        self.generateVariables()
        self.generateConstraints()
        self.model.update()
        self.generateObjective()
        self.setStartSolution()
        self.model.update()

    def generateVariables(self):
        self.slack = self.model.addVars(self.days, self.shifts, vtype=gu.GRB.CONTINUOUS, lb=0, name='slack')
        self.motivation_i = self.model.addVars(self.physicians, self.days, self.shifts, self.roster,
                                               vtype=gu.GRB.CONTINUOUS, lb=0, ub=1, name='motivation_i')
        self.lmbda = self.model.addVars(self.physicians, self.roster, vtype=gu.GRB.BINARY, lb=0, name='lmbda')

    def generateConstraints(self):
        for i in self.physicians:
            self.cons_lmbda[i] = self.model.addConstr(gu.quicksum(self.lmbda[i, r] for r in self.roster) == 1)
        for t in self.days:
            for s in self.shifts:
                self.cons_demand[t, s] = self.model.addConstr(
                    gu.quicksum(self.motivation_i[i, t, s, r]*self.lmbda[i, r] for i in self.physicians for r in self.roster) +
                    self.slack[t, s] >= self.demand[t, s])
        return self.cons_lmbda, self.cons_demand

    def generateObjective(self):
        self.model.setObjective(gu.quicksum(self.slack[t, s] for t in self.days for s in self.shifts),
                                sense=gu.GRB.MINIMIZE)

    def solveRelaxModel(self):
        self.model.Params.QCPDual = 1
        for v in self.model.getVars():
            v.setAttr('vtype', 'C')
        self.model.optimize()

    def getDuals_i(self):
        Pi_cons_lmbda = self.model.getAttr("Pi", self.cons_lmbda)
        return Pi_cons_lmbda

    def getDuals_ts(self):
        Pi_cons_demand = self.model.getAttr("QCPi", self.cons_demand)
        return Pi_cons_demand

    def getObjValues(self):
        obj = self.model.objVal
        return obj

    def updateModel(self):
        self.model.update()

    def addColumn(self, newSchedule, iter, index):
        self.newvar = {}
        colName = f"ScheduleUsed[{index},{iter}]"
        newScheduleList = []
        cons_demandList = []
        for i, t, s, r in newSchedule:
            newScheduleList.append(newSchedule[i, t, s, r])
        rounded_ScheduleList = ['%.2f' % elem for elem in newScheduleList]
        Column = gu.Column(rounded_ScheduleList, newcon)
        self.newvar = self.model.addVar(vtype=gu.GRB.CONTINUOUS, lb=0, column=Column, name=colName)
        self.model.update()

    def setStartSolution(self):
        startValues = {}
        for i, t, s, r in itertools.product(self.physicians, self.days, self.shifts, self.roster):
            startValues[(i, t, s, r)] = 0
        for i, t, s, r in startValues:
            self.motivation_i[i, t, s, r].Start = startValues[i, t, s, r]

    def solveModel(self, timeLimit, EPS):
        self.model.setParam('TimeLimit', timeLimit)
        self.model.setParam('MIPGap', EPS)
        self.model.Params.QCPDual = 1
        self.model.Params.OutputFlag = 0
        self.model.optimize()
        self.model.write("d.lp")


    def writeModel(self):
        self.model.write("master.lp")

    def File2Log(self):
        self.model.Params.LogToConsole = 1
        self.model.Params.LogFile = "./log.txt"

    def getObjVal(self):
        obj = self.model.getObjective()
        value = obj.getValue()
        return value

    def finalSolve(self, timeLimit, EPS):
        self.model.setParam('TimeLimit', timeLimit)
        self.model.setParam('MIPGap', EPS)
        self.model.setAttr("vType", self.lmbda, gu.GRB.INTEGER)
        self.model.update()
        self.model.optimize()
        self.model.write("dd.lp")
        if self.model.status == GRB.OPTIMAL:
            print("Optimal solution found")
            for i in self.physicians:
                for t in self.days:
                    for s in self.shifts:
                        for r in self.roster:
                            print(f"Nurse {i}: Motivation {self.motivation_i[i, t, s, r].x} in Shift {s} on day {t}")
        else:
            print("No optimal solution found.")


    def modifyConstraint(self):
        for t in self.days:
            for s in self.shifts:
                self.newcoef = 1.0
                current_cons = self.cons_demand[t, s]
                qexpr = self.model.getQCRow(current_cons)
                new_var = self.newvar
                new_coef = self.newcoef
                qexpr.add(new_var, new_coef)
                rhs = current_cons.getAttr('RHS')
                sense = current_cons.getAttr('Sense')
                name = current_cons.getAttr('ConstrName')
                newcon = self.model.addQConstr(qexpr, sense, rhs, name)
                self.model.removeConstr(current_cons)
                self.cons_demand[t, s] = newcon
                return newcon
class Subproblem:
    def __init__(self, duals_i, duals_ts, dfData, i, M, iteration):
        self.days = dfData['T'].dropna().astype(int).unique().tolist()
        self.shifts = dfData['K'].dropna().astype(int).unique().tolist()
        self.duals_i = duals_i
        self.duals_ts = duals_ts
        self.Max = 5
        self.Min = 2
        self.M = M
        self.alpha = 0.5
        self.model = gu.Model("Subproblem")
        self.index = i
        self.it = iteration

    def buildModel(self):
        self.generateVariables()
        self.generateConstraints()
        self.generateObjective()
        print(f"Index: {self.index}")
        self.model.update()

    def generateVariables(self):
        self.x = self.model.addVars([self.index], self.days, self.shifts, vtype=GRB.BINARY, name='x')
        self.y = self.model.addVars([self.index], self.days, vtype=GRB.BINARY, name='y')
        self.mood = self.model.addVars([self.index], self.days, vtype=GRB.CONTINUOUS, lb=0, name='mood')
        self.motivation = self.model.addVars([self.index], self.days, self.shifts, [self.it], vtype=GRB.CONTINUOUS, lb=0, name='motivation')

    def generateConstraints(self):
        for i in [self.index]:
            for t in self.days:
                self.model.addConstr(self.mood[i, t] == 1 - self.alpha * self.y[i, t])
                self.model.addConstr(quicksum(self.x[i, t, s] for s in self.shifts) == self.y[i, t])
                self.model.addConstr(gu.quicksum(self.x[i, t, s] for s in self.shifts) <= 1)

            for t in range(1, len(self.days) - self.Max + 1):
                self.model.addConstr(gu.quicksum(self.y[i, u] for u in range(t, t + 1 + self.Max)) <= self.Max)
            self.model.addLConstr(quicksum(self.y[i, t] for t in self.days) >= self.Min)
            for t in self.days:
                for s in self.shifts:
                    self.model.addLConstr(self.motivation[i, t, s, self.it] >= self.mood[i, t] - self.M * (1 - self.x[i, t, s]))
                    self.model.addLConstr(self.motivation[i, t, s, self.it] <= self.mood[i, t] + self.M * (1 - self.x[i, t, s]))
                    self.model.addLConstr(self.motivation[i, t, s, self.it] <= self.x[i, t, s])

    def generateObjective(self):
        self.model.setObjective(
            0 - gu.quicksum(self.motivation[i, t, s, self.it] * self.duals_ts[t, s] for i in [self.index] for t in self.days for s in self.shifts) -
            self.duals_i[self.index], sense=gu.GRB.MINIMIZE)

    def getNewSchedule(self):
        return self.model.getAttr("X", self.motivation)

    def getObjVal(self):
        obj = self.model.getObjective()
        value = obj.getValue()
        return value

    def getStatus(self):
        return self.model.status

    def solveModel(self, timeLimit, EPS):
        self.model.setParam('TimeLimit', timeLimit)
        self.model.setParam('MIPGap', EPS)
        self.model.Params.OutputFlag = 0
        self.model.optimize()
        if self.model.status == GRB.OPTIMAL:
            print("Optimal solution found")
            for i in [self.index]:
                for t in self.days:
                    for s in self.shifts:
                        print(f"Physician {self.index}: Motivation {self.x[i, t, s].x} in Shift {s} on day {t}")
        else:
            print("No optimal solution found.")


#### Column Generation
# CG Prerequisites
modelImprovable = True
t0 = time.time()
max_itr = 2
itr = 0

# Lists
objValHistSP = []
objValHistRMP = []

# Build & Solve MP
master = MasterProblem(DataDF, Demand_Dict, itr)
master.buildModel()
master.File2Log()
master.updateModel()
master.solveRelaxModel()

# Get Duals from MP
duals_i = master.getDuals_i()
duals_ts = master.getDuals_ts()

print('*         *****Column Generation Iteration*****          \n*')
while (modelImprovable) and itr < max_itr:
    # Start
    itr += 1
    print('*Current CG iteration: ', itr)

    # Solve RMP
    master.solveRelaxModel()
    objValHistRMP.append(master.getObjValues())
    print('*Current RMP ObjVal: ', objValHistRMP)


    # Get Duals
    duals_i = master.getDuals_i()
    duals_ts = master.getDuals_ts()

    # Solve SPs
    modelImprovable = False
    for index in I_list:
        subproblem = Subproblem(duals_i, duals_ts, DataDF, index, 1e6, itr)
        subproblem.buildModel()
        subproblem.solveModel(3600, 1e-6)
        status = subproblem.getStatus()
        if status != 2:
            raise Exception("Pricing-Problem can not reach optimality!")
        reducedCost = subproblem.getObjVal()
        objValHistSP.append(reducedCost)
        print('*Reduced cost', reducedCost)
        if reducedCost < 1e-6:
            ScheduleCuts = subproblem.getNewSchedule()
            master.addColumn(ScheduleCuts, itr, index)
            master.modifyConstraints()
            master.updateModel()
            modelImprovable = True
    master.updateModel()

# Solve MP
master.finalSolve(3600, 0.01)

How can i fix this problem?

$\endgroup$

1 Answer 1

0
$\begingroup$

On line 91, in the function AddColumn you use newcon without defining it first.

$\endgroup$
2
  • $\begingroup$ I know, thanks. newcon gets defined in modify constraint(). But how do I need to change the code that addcolumn() gets "access" to this constraint? I updated the OP for more details. $\endgroup$ Commented Feb 24 at 19:46
  • $\begingroup$ The issue is just scope. If you want AddColumn() to have access to newcon you either need to pass newcon into the function, or you could make it an attribute of the MasterProblem class. But I will also say that in your main code, you call AddColumn() before you call ModifyConstraints(), so newcon still isn't going to be defined in time. $\endgroup$ Commented Feb 26 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.