0

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(&quot;Pricing-Problem can not reach optimality!&quot;)
    reducedCost = subproblem.getObjVal()
    objValHistSP.append(reducedCost)
    print('*Reduced cost', reducedCost)
    if reducedCost &lt; 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?

nflgreaternba
  • 99
  • 1
  • 8

1 Answers1

0

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

NaturalLogZ
  • 119
  • 4
  • 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. – nflgreaternba Feb 24 '24 at 19:46
  • 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. – NaturalLogZ Feb 26 '24 at 14:53