Transfering a solution of binary variables into right order
回答済みHello everyone,
I just startet optimizing with Python and try to solve a small model of sequencing and scheduling surgeries.
With the help of the binary variable "sequencing", I try to define the order of surgeries.
When I solve the model, the optimal solution is:
sequencing[surg1,surg2] 1
sequencing[surg3,surg5] 1
sequencing[surg4,surg1] 1
sequencing[surg5,surg4] 1
Now I am wondering, if it is possible to tranfer these binary variables into the right order of surgeries. Maybe a List or a Comment like:
Surgery_order: surg3 --> surg5 --> surg4 --> surg1 --> surg2
____________________________________________________
The whole code is:
import gurobipy as gp
from gurobipy import GRB #Gurobi Python Modul
#--------------------------------------------------------------#
#Parameters
surgeries = ['surg1', 'surg2','surg3','surg4','surg5' ]
n = len(surgeries)
costs_waiting = 3 #waiting time costs per minute
costs_idle_time = 5 #idle time costs per minute
costs_tardiness = 4 #tardniess costs per minute
duration_OR = 200 #planned duration for which the OR will be utilized in minutes
M = 700 #big number; upper bound for surgery completion time
#duration for each surgery in minutes
duration = {'surg1': 60,'surg2': 90,'surg3': 10,'surg4': 21,'surg5': 30,}
#--------------------------------------------------------------#
#Model Deployment
m = gp.Model ('two-stage stochastic MIP')
start_time = m.addVars(surgeries, name="start_time")
sequencing = m.addVars(surgeries, surgeries, vtype=GRB.BINARY, name="sequencing")
waiting_time = m.addVars(surgeries, surgeries, name="waiting_time") #scenario fehlt
idle_time = m.addVars(surgeries, surgeries, name="idle_time") #scenario fehlt
tardiness = m.addVar(name="tardiness")
earliness = m.addVar(name="earliness")
# Constraints
waiting_times = m.addConstrs((waiting_time[i,j] - M * sequencing[i,j] <= 0 for i in surgeries for j in surgeries), name = "waiting")
idle_times = m.addConstrs((idle_time[i,j] - M * sequencing[i,j] <= 0 for i in surgeries for j in surgeries), name = "idle_time")
completness = m.addConstrs((sequencing.sum(i,'*') <= 1 for i in surgeries), name = "completness")
no_doubles = m.addConstrs(sequencing[i,j] == 0 for i in surgeries for j in surgeries if i==j)
subtours = m.addConstr ((gp.quicksum(sequencing[i,j] for i in surgeries for j in surgeries) == n-1),name = "subtours")
balance_waiting_idling = m.addConstrs((- waiting_time.sum('*',i) + waiting_time.sum(i,'*') - idle_time.sum(i,'*') + start_time[i] == duration[i] for i in surgeries), name = "balance_tardiness_earliness")
balance_tardiness_earliness = m.addConstr ((sum(duration.values()) + gp.quicksum(idle_time[i,j] for i in surgeries for j in surgeries) - tardiness + earliness == duration_OR), name = "balance_tardiness_earliness")
#objective function
objective = m.setObjective(gp.quicksum(waiting_time[i,j] * costs_waiting + idle_time[i,j] * costs_idle_time for i in surgeries for j in surgeries) + tardiness * costs_tardiness, GRB.MINIMIZE)
#--------------------------------------------------------------#
#optimization
m.optimize()
m.printAttr ('x')
print ('--> Minimal total costs:', m.objval)
Best regards
Alice
-
正式なコメント
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
The code below creates a list \( \texttt{surgs} \) that contains the surgeries, ordered by precedence.
# Extract indices (tuples) from sequencing variables equal to 1 in solution
seq = [k for k, v in sequencing.items() if v.X > 0.5]
# Determine starting surgery
s1, s2 = zip(*seq)
surgs = [a for a in s1 if a not in s2]
# Iteratively add next sequential surgery
while len(surgs) < len(seq) + 1:
surgs += [b for a, b in seq if a == surgs[-1]]
# Display results
print(" --> ".join(surgs))What it does:
- Builds \( \texttt{seq} \), the list of tuples corresponding to \( \texttt{sequencing} \) variables equal to \( 1 \) in the optimal solution.
- Finds the first surgery, which is the first element of tuple in \( \texttt{seq} \) that is not the second element of any tuple in \( \texttt{seq} \).
- Iteratively adds the next surgery to \( \texttt{surgs} \). This is always the second element of a tuple in \( \texttt{seq} \) whose first element equals the last element of \( \texttt{surgs} \).
1 -
-
Hey Eli,
Thanks a lot! It's working :)
The explanation is great!
0 -
-
Hey Eli,
one more question. I try to add the start times into the sequence, but it's not really working.
The first surgery should start at time 0, the second at start_time 1, the third at start_time 1+2 and so on.
The result should look like this (if it is possible)
surg3 [start: 0] --> surg5 [start: 10] --> surg4 [start: 40] --> surg1 [start: 61] --> surg2 [start: 121]
My solution so far is:
Variable x ------------------------- start_time[surg1] 60 start_time[surg2] 90 start_time[surg3] 10 start_time[surg4] 21 start_time[surg5] 30 sequencing[surg1,surg2] 1 sequencing[surg3,surg5] 1 sequencing[surg4,surg1] 1 sequencing[surg5,surg4] 1 tardiness 11 ____________________________________ Minimal total costs: 44.0 Optimal sequence of surgeries: surg3 --> surg5 --> surg4 --> surg1 --> surg2
Best regards,
Alice
0 -
-
-
We can build a list \( \texttt{starts} \) of the same length as list \( \texttt{surgs} \) that stores the cumulative elapsed time before each surgery starts:
# Extract indices (tuples) from sequencing variables equal to 1 in solution
seq = [k for k, v in sequencing.items() if v.X > 0.5]
# Determine starting surgery
s1, s2 = zip(*seq)
surgs = [a for a in s1 if a not in s2]
# Iteratively add next sequential surgery and track cumulative time
starts = [0]
while len(surgs) < len(seq) + 1:
starts.append(starts[-1] + start_time[surgs[-1]].X)
surgs += [b for a, b in seq if a == surgs[-1]]
# Display results
print(" --> ".join([f"{s} [start: {t}]" for s, t in zip(surgs, starts)]))The output:
surg3 [start: 0] --> surg5 [start: 10.0] --> surg4 [start: 40.0] --> surg1 [start: 61.0] --> surg2 [start: 121.0]1 -
-
Thank you for your help, Eli!
0 -
投稿コメントは受け付けていません。
コメント
6件のコメント