derpythonnoob2
Newbie
- Registriert
- Feb. 2024
- Beiträge
- 1
Hallo, ich möchte folgendes Scheduling in Python mit Gurobi mit Column Generation lösen.
Die Indizes sind i ∈ I Krankenschwestern, s ∈ S Schichten und t ∈ T Tage. Die Entscheidungsvariablen sind:
Die Parameter / Inputs sind:
Nun zum Teil der Spaltengenerierung:
Das ist mein Code bisher:
Leider habe ich noch ein paar Probleme. Es geht mir vor allem um die folgenden Dinge.
1) Wie führe ich den Index R richtig ein und wie modelliere ich die Interaktion mit λ und perf im MP?
2) Ist die Berechnung der reduzierten Kosten korrekt?
3) Wie füge ich neue Spalten (in diesem Fall Dienstpläne) in das Masterproblem ein?
Ich wäre wirklich dankbar für jede Hilfe!
Die Indizes sind i ∈ I Krankenschwestern, s ∈ S Schichten und t ∈ T Tage. Die Entscheidungsvariablen sind:
- x_{its}= 1, wenn die Krankenschwester i die Schicht s am Tag t arbeitet
- slack_{ts}: Slack für Schicht s am Tag t
- motivation_{its}: für Krankenschwester i in Schicht s am Tag t
- mood_{it} für Krankenschwester i am Tag t
Die Parameter / Inputs sind:
- Demand_{ts}: Bedarf pro Schicht s am Tag t
- α: Zufallszahl ∈[ 0,1]
- M: Große Zahl
- Max_W: Anzahl der maximal erlaubten aufeinanderfolgenden Arbeitstage
Nun zum Teil der Spaltengenerierung:
- r: Index für Dienstpläne/Raster (eine machbare Zuordnung von Schichten zu einer Pflegekraft für den Planungshorizont)
- R(i): Menge der alternativen Dienstpläne für Krankenschwester i
- motivation^r_{its}: Motivation der Krankenschwester i wird der Schicht s im Plan r am Tag d zugewiesen.
Das ist mein Code bisher:
Code:
from gurobipy import *
import gurobipy as gu
import pandas as pd
import itertools
# 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):
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.demand = DemandDF
self.model = gu.Model("MasterProblem")
def buildModel(self):
self.generateVaraibles()
self.generateConstraints()
self.generateObjective()
self.setStartSolution()
self.model.update()
def generateVaraibles(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, name = 'motivation_i')
self.lmbda = self.model.addVars(self.physicians, self.roster, vtype=gu.GRB.INTEGER, lb = 0, name = 'lmbda')
def generateConstraints(self):
self.cons_lmbda = {}
for i in self.physicians:
self.cons_lmbda[i] = self.model.addLConstr(gu.quicksum(self.lmbda[i, r] for r in self.roster) == 1)
return self.cons_lmbda
self.cons_demand = {}
for t in self.days:
for s in self.shifts:
self.cons_demand[t,s] = self.model.addLConstr(gu.quicksum(self.motivation_i[i, t, s, r] for r in self.roster for i in self.physicians) + self.slack[t, s] >= self.demand[t, s])
return 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.relaxedModel = self.model.relax()
self.relaxedModel.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("Pi", self.cons_demand)
return Pi_cons_demand
def addColumn(self, objective, newSchedule):
ctName = ('ScheduleUseVar[%s]' %len(self.model.getVars()))
newColumn = gu.column(newSchedule, self.model.getConstrs())
self.model.addVar(vtype = gu.GBR.INTEGER, lb = 0, obj = objective, column = newColumn, name = ctName)
self.model.update()
def setStartSolution(self):
startValues = {}
for i, t, s in itertools.product(self.physicians, self.days, self.shifts):
startValues[(i, t, s)] = 0
for i, t, s in startValues:
self.motivation_i[i, t, s].Start = startValues[i, t, s]
class Subproblem:
def __init__(self, duals_i, duals_ts, dfData):
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.M = 100
self.alpha = 0.5
self.model = gu.Model("Subproblem")
def buildModel(self):
self.generateVariables()
self.generateConstraints()
self.generateObjective()
self.model.update()
def generateVariables(self):
self.x = self.model.addVars(self.days, self.shifts, vtype=GRB.BINARY, name='x')
self.mood = self.model.addVars(self.days, vtype=GRB.CONTINUOUS, lb = 0, ub = 1, name='mood')
self.motivation = self.model.addVars(self.days, self.shifts, vtype=GRB.CONTINUOUS, lb = 0, ub = 1, name='motivation')
def generateConstraints(self):
for t in self.days:
self.model.addLConstr(self.mood[t] == 1 - self.alpha * quicksum(self.x[t, s] for s in self.shifts))
for t in self.days:
self.model.addLConstr(gu.quicksum(self.x[t, s] for s in self.shifts) <= 1)
for t in range(1, len(self.days) - self.Max + 2):
self.model.addLConstr(gu.quicksum(self.x[i, u, s] for s in self.shifts for u in range(t, t + 1 + self.Max)) <= self.Max)
for t in self.days:
for s in self.shifts:
self.model.addLConstr(self.mood[t] + self.M*(1-self.x[t, s]) >= self.motivation[t, s])
self.model.addLConstr(self.motivation[t, s] >= self.mood[t] - self.M * (1 - self.x[t, s]))
self.model.addLConstr(self.motivation[t, s] <= self.x[t, s])
def generateObjective(self):
self.model.setObjective(0-gu.quicksum(self.motivation[t,s]*self.duals_ts[t,s] for s in self.shifts for t in self.days)-self.duals_i[i], sense = gu.GRB.MINIMIZE)
def getNewSchedule(self):
return self.model.getAttr("X", self.model.getVars())
#class InitialScheduleGenerator:
# def __init__(self, nbPhysicians, nbDays, nbShifts):
# columns = ['Value', 'Physician', 'Days', 'Shifts']
# patterns = pd.DataFrame(columns=columns)
# self.patternDf = patterns
# self.nbPhysicians = nbPhysicians
# self.nbDays = nbDays
# self.nbShifts = nbShifts
# def generateBasicInitialSchedule(self):
# self.patternDf['Value'] = 0
# combinations = list(itertools.product(range(1, self.nbPhysicians + 1),
# range(1, self.nbDays + 1),
# range(1, self.nbShifts + 1)))
# self.patternDf['Physician'], self.patternDf['Days'], self.patternDf['Shifts'] = zip(*combinations)
# return self.patternDf
def solveModel(self, timeLimit, EPS):
self.model.setParam('TimeLimit', timeLimit)
self.model.setParam('MIPGap', EPS)
self.model.optimize()
### CG Sequence
#Initizalie Basic Solution
scheduleGenerator = InitialScheduleGenerator(3,7, 3)
scheduleDf = scheduleGenerator.generateBasicInitialSchedule()
#Build MP
master = MasterProblem(DataDF, Demand_Dict)
master.buildModel()
modelImprovable = True
while (modelImprovable):
master.solveRelaxModel()
duals_i = master.getDuals_i()
duals_ts = master.getDuals_ts()
for i in I:
subproblem = Subproblem(duals_i, duals_ts, DataDF)
subproblem.buildModel()
subproblem.solveModel(3600, 1e-6)
modelImprovable = (subproblem.getObjectiveValue) < -1e-6
newScheduleCost = 1
newScheduleCuts = subproblem.getNewSchedule()
master.addColumn(newScheduleCost, newScheduleCuts)
master.solveModel(3600, 0.01)Leider habe ich noch ein paar Probleme. Es geht mir vor allem um die folgenden Dinge.
1) Wie führe ich den Index R richtig ein und wie modelliere ich die Interaktion mit λ und perf im MP?
2) Ist die Berechnung der reduzierten Kosten korrekt?
3) Wie füge ich neue Spalten (in diesem Fall Dienstpläne) in das Masterproblem ein?
Ich wäre wirklich dankbar für jede Hilfe!
