Multiple Objective Functions with Priority
AnsweredHello, I am trying a optimize a problem where I have routes determined for resources and want to update them with the primary objective of minimizing the maximum expected routing time and the secondary aim of minimizing the total routing time. A list named V_move states the points in the routes considered to be moved and detour positions are the considered positions to insert those moved points from V_move. K_hold are the resources which are considered for having point(s) added to their route from the list V_move and K_move are the resources considered for point(s) removed from their route.
the inputs are - t_add[i][j] stating how much time should be added if point i from V_move is added at detour position j, y_insertion[k][i] (binary) stating if resource k in K_hold has the detour position, and t_deduct[k][i] stating how much time should be educated if i in V_move is removed from the route of resource k.
The following is the code I have written -
import gurobipy as gp
from gurobipy import GRB
from itertools import product
#Declare the model for the insertion IP
m_insertion = gp.Model()
m_insertion.ModelSense = GRB.MINIMIZE
m_insertion.Params.LogToConsole = 0
#Declare ranges
v_move_range = range(len(V_move))
detour_pos_range = range(len(t_add[0]))
### DECISION VARIABLES IP INSERTION ##
#Declare decision variable xij
x_insertion = []
for i in v_move_range:
x_insertion.append([])
for j in detour_pos_range:
x_insertion[i].append(m_insertion.addVar(vtype = GRB.BINARY))
# Declare decision variable t_expupdated - this captures the updated routing time
t_expupdated = []
for i in range (num_cob+num_ded):
t_expupdated.append(m_insertion.addVar(lb=0.0, vtype=GRB.CONTINUOUS))
# Declare decision variable z_upbound - this is here to create an upper bound for all t_expupdated which can be minimized for the primary objective
z_upbound = m_insertion.addVar(lb=0.0, vtype=GRB.CONTINUOUS)
#Primary Objective
m_insertion.setObjectiveN(z_upbound + gp.quicksum(t_expupdated[i] for i in range(num_cob + num_ded)) , index=0, priority =2, abstol = 0.00)
#Secondary Objective
m_insertion.setObjectiveN(gp.quicksum(t_expupdated[i] for i in range(num_cob + num_ded)), index=1, priority =1)
### CONSTRAINTS IP INSERTION ##
#The total expected time after adding a point to K_hold should not exceed the current slack time
for k in K_hold:
m_insertion.addConstr(gp.quicksum(x_insertion[i][j]*t_add[i][j]*y_insertion[k][j] for i in range(len(V_move)) \
for j in detour_pos_range) <= slack_time_rev[k])
#A detour position can not insert more than one stopping point
for j in detour_pos_range:
m_insertion.addConstr(gp.quicksum(x_insertion[i][j] for i in v_move_range) <= 1)
# A stopping point in V_move cannot be inserted into more than one detour position
for i in v_move_range:
m_insertion.addConstr(gp.quicksum(x_insertion[i][j] for j in detour_pos_range) <= 1)
#Additional Constraint - NEEDS TO BE REMOVED
# for i in v_move_range:
# m_insertion.addConstr(x_insertion[i][num_detour_positions-1] == 0)
# Calculating of total expected waiting time after adding to the resources of K_hold
for k in K_hold:
m_insertion.addConstr(t_expupdated[k]==exp_pick_comp_time[k] +\
gp.quicksum(x_insertion[i][j]*t_add[i][j]*y_insertion[k][j] for i in v_move_range for j in detour_pos_range))
#Calculating of total expected waiting time after removing from a sequence of K_move
for k in K_move:
m_insertion.addConstr(t_expupdated[k] == exp_pick_comp_time[k] - sum(t_deduct[k][i]*x_insertion[i][j] for i in v_move_range))
#The resources which are not part of K_move or K_hold, exp pick comp time remain unchanged
K_unchanged = list(set([i for i in range (num_cob + num_ded)]) - set(K_hold) -set(K_move))
if len(K_unchanged) != 0:
for k in K_unchanged:
m_insertion.addConstr(t_expupdated[k] == exp_pick_comp_time[k])
#Setting an upper bound for each of the updated expected travel time
for k in range(num_cob + num_ded):
m_insertion.addConstr(z_upbound >= t_expupdated[k])
### IP INSERTION - OPTIMIZATION AND RESULT ###
if m_insertion.status == GRB.OPTIMAL:
print(f' updated maximum expected pick completion time: {m_insertion.ObjVal}')
print(f' max pick comp time improvement: {max(exp_pick_comp_time) - m_insertion.ObjVal} seconds')
insertion_improvement.append(max(exp_pick_comp_time) - m_insertion.ObjVal)
for i in v_move_range:
for j in detour_pos_range:
if x_insertion[i][j].X > 0.001:
print(f'stopping point {V_move[i]} is inserted into detour position {j} out of {len(t_add[0])} det pos')
However, the output of this model is always choosing the last index of j for x_insertion[i][j] in the optimal result even if the best detour position is not the last detour position. The primary objective seems to be satisfied, but the secondary objective clearly can have better results by manually looking at the inputs but it clearly is not doing so. Can you please advise what might be the problem?
0
-
-
Gurobi Staff
Hi Joyjit,
Based on your description I would expect the primary objective to only contain \(\texttt{z_upbound}\), without the sum of all entries of \(\texttt{t_expupdated}\).
Otherwise, I am not able to run your code example. Could you please provide a minimal reproducible example? See Tutorial: Preparing a Minimal Reproducible Example – Gurobi Help Center
Best regards,
Lennart0 -
-
Hello Lennart,
Thank you for getting back to me. Apologies, for the confusion in the objective function, I had copied something from my previous model. Even with the objective function update as you suggested the same problem persists. I have prepared a MRE model which you can check to help me identify the problem as follows -
#Data Inputs
exp_pick_comp_time = [2412.459325024837, 2252.283005646575, 2543.8655009238464, 1428.3333333333333]
slack_time_rev = [131.4061758990092, 291.5824952772714, 0.0, 1115.5321675905132]
K_move = [0, 1, 2]
K_hold = [3]
num_cob = 3
num_ded = 1
V_move = [112, 107, 77, 93, 69, 83, 108, 50, 61, 78, 123, 86, 36, 16, 121, 31, 120, 54]
dict_time_reduction_V_move= {112: 299.7113402061856, 107: 216.44827586206895, \
77: 215.68067226890756, 93: 705.5384615384614, \
69: 248.42268041237116, 83: 125.11904761904762, \
108: 315.6578947368421, 50: 141.44827586206895, \
61: 120.19469026548671, 78: 95.19469026548671, \
123: 472.0697674418605, 86: 479.26530612244903, \
36: 198.1578947368421, 16: 266.6190476190476, \
121: 316.35087719298247, 31: 384.68067226890753, \
120: 239.69565217391303, 54: 279.6666666666667}
t_add = [[241.66666666666669, 258.33333333333337, 291.6666666666667, 308.33333333333337, 311.6666666666667, 341.6666666666667, 328.33333333333337, 181.66666666666666, 195.0, 175.0, 175.0, 195.0, 161.66666666666669, 215.0, 251.66666666666669, 225.0, 141.66666666666669], [120.00000000000001, 103.33333333333334, 103.33333333333333, 100.0, 83.33333333333334, 126.66666666666667, 146.66666666666669, 83.33333333333334, 163.33333333333334, 183.33333333333334, 203.33333333333334, 240.00000000000003, 223.33333333333331, 243.33333333333334, 263.3333333333333, 270.0, 123.33333333333334], [70.0, 86.66666666666667, 136.66666666666669, 150.0, 126.66666666666667, 140.0, 116.66666666666667, 50.0, 163.33333333333334, 200.00000000000003, 220.00000000000003, 223.33333333333334, 190.0, 243.33333333333334, 296.6666666666667, 270.0, 90.0], [233.33333333333334, 233.33333333333334, 250.00000000000003, 266.6666666666667, 270.0, 313.33333333333337, 316.6666666666667, 173.33333333333334, 170.0, 133.33333333333331, 133.33333333333331, 170.0, 153.33333333333331, 190.0, 210.0, 200.0, 133.33333333333334], [111.66666666666667, 61.66666666666667, 45.0, 41.66666666666667, 25.0, 68.33333333333333, 91.66666666666667, 28.33333333333333, 105.0, 125.00000000000001, 145.0, 181.66666666666669, 165.0, 185.0, 205.0, 245.0, 98.33333333333337], [213.33333333333334, 230.0, 273.3333333333333, 280.0, 220.0, 196.66666666666669, 173.33333333333334, 150.0, 306.6666666666667, 343.33333333333337, 363.33333333333337, 366.6666666666667, 333.3333333333333, 386.6666666666667, 433.3333333333333, 406.6666666666667, 233.33333333333337], [381.6666666666667, 346.6666666666667, 330.0, 346.6666666666667, 350.0, 393.3333333333333, 416.6666666666667, 273.33333333333337, 250.0, 230.00000000000003, 210.00000000000003, 226.66666666666669, 190.0, 170.0, 130.0, 95.0, 128.33333333333337], [218.33333333333334, 218.33333333333334, 235.00000000000003, 251.66666666666669, 255.0, 298.3333333333333, 301.6666666666667, 158.33333333333334, 155.0, 135.0, 115.0, 115.0, 78.33333333333333, 58.33333333333334, 58.33333333333333, 65.0, 58.33333333333334], [101.66666666666667, 118.33333333333334, 151.66666666666669, 168.33333333333334, 171.66666666666669, 201.66666666666669, 188.33333333333334, 25.0, 58.33333333333334, 111.66666666666667, 131.66666666666669, 135.0, 101.66666666666667, 155.0, 191.66666666666669, 165.0, 41.666666666666686], [85.0, 101.66666666666667, 151.66666666666669, 185.0, 181.66666666666669, 195.00000000000003, 171.66666666666669, 25.0, 58.33333333333334, 95.0, 115.0, 118.33333333333333, 85.0, 138.33333333333334, 191.66666666666669, 165.0, 25.0], [113.33333333333334, 130.0, 180.00000000000003, 193.33333333333334, 138.33333333333334, 120.0, 96.66666666666667, 61.66666666666666, 206.66666666666669, 243.33333333333334, 263.33333333333337, 266.6666666666667, 233.33333333333331, 286.6666666666667, 340.0, 313.33333333333337, 133.33333333333337], [288.33333333333337, 238.33333333333337, 205.00000000000003, 205.0, 225.0, 285.0, 308.3333333333333, 165.0, 141.66666666666669, 121.66666666666667, 101.66666666666667, 118.33333333333333, 81.66666666666667, 61.66666666666667, 25.0, 45.0, 75.0], [398.33333333333337, 363.33333333333337, 346.6666666666667, 363.33333333333337, 366.6666666666667, 410.0, 433.3333333333333, 290.0, 266.6666666666667, 246.66666666666669, 226.66666666666669, 243.33333333333334, 206.66666666666669, 186.66666666666669, 146.66666666666669, 111.66666666666667, 145.0], [111.66666666666667, 115.0, 135.0, 131.66666666666669, 71.66666666666667, 48.33333333333333, 36.66666666666667, 36.66666666666667, 191.66666666666669, 215.00000000000003, 235.00000000000003, 251.66666666666669, 231.66666666666669, 271.6666666666667, 295.0, 281.6666666666667, 131.66666666666669], [121.66666666666667, 138.33333333333334, 171.66666666666669, 188.33333333333334, 191.66666666666669, 221.66666666666669, 208.33333333333334, 61.66666666666666, 58.33333333333334, 75.0, 111.66666666666667, 115.0, 81.66666666666667, 135.0, 171.66666666666669, 145.0, 41.666666666666686], [78.33333333333334, 78.33333333333334, 95.0, 91.66666666666667, 75.0, 118.33333333333333, 121.66666666666667, 58.33333333333334, 155.0, 175.00000000000003, 195.00000000000003, 215.00000000000003, 198.33333333333331, 235.0, 255.0, 245.0, 98.33333333333337], [325.00000000000006, 316.6666666666667, 325.0, 341.6666666666667, 345.0, 388.3333333333333, 400.0, 256.66666666666663, 245.00000000000003, 225.00000000000003, 205.00000000000003, 213.33333333333334, 176.66666666666669, 165.0, 125.00000000000001, 63.33333333333334, 96.66666666666669], [311.6666666666667, 296.6666666666667, 298.3333333333333, 315.0, 318.33333333333337, 361.6666666666667, 380.0, 236.66666666666666, 218.33333333333334, 198.33333333333334, 178.33333333333334, 193.33333333333334, 156.66666666666669, 138.33333333333334, 98.33333333333333, 43.33333333333334, 76.66666666666669]]
t_deduct = [[299.7113402061856, 216.44827586206895, 215.68067226890756, 705.5384615384614, 248.42268041237116, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 125.11904761904762, 315.6578947368421, 141.44827586206895, 120.19469026548671, 95.19469026548671, 472.0697674418605, 479.26530612244903, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 198.1578947368421, 266.6190476190476, 316.35087719298247, 384.68067226890753, 239.69565217391303, 279.6666666666667], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
y_insertion = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
#Import Packages
import gurobipy as gp
from gurobipy import GRB
from itertools import product
#Declare the model for the insertion IP
m_insertion = gp.Model()
m_insertion.ModelSense = GRB.MINIMIZE
m_insertion.Params.LogToConsole = 0
#Declare ranges
v_move_range = range(len(V_move))
detour_pos_range = range(len(t_add[0]))
#Define Decision Variable x_insertion
x_insertion = []
for i in v_move_range:
x_insertion.append([])
for j in detour_pos_range:
x_insertion[i].append(m_insertion.addVar(vtype = GRB.BINARY))
# Declare decision variable t_expupdated
t_expupdated = []
for i in range (num_cob+num_ded):
t_expupdated.append(m_insertion.addVar(lb=0.0, vtype=GRB.CONTINUOUS))
# Declare decision variable z_upbound
z_upbound = m_insertion.addVar(lb=0.0, vtype=GRB.CONTINUOUS)
#Primary Objective
m_insertion.setObjectiveN(z_upbound, index=0, priority =2, abstol = 0.00)
#Secondary Objective
m_insertion.setObjectiveN(gp.quicksum(t_expupdated[i] for i in range(num_cob + num_ded)), index=1, priority =1)
### CONSTRAINTS ###
#The total expected time after adding a point to K_hold should not exceed the current slack time
for k in K_hold:
m_insertion.addConstr(gp.quicksum(x_insertion[i][j]*t_add[i][j]*y_insertion[k][j] for i in range(len(V_move)) \
for j in detour_pos_range) <= slack_time_rev[k])
#A detour position can not insert more than one stopping point
for j in detour_pos_range:
m_insertion.addConstr(gp.quicksum(x_insertion[i][j] for i in v_move_range) <= 1)
# A stopping point in V_move cannot be inserted into more than one detour position
for i in v_move_range:
m_insertion.addConstr(gp.quicksum(x_insertion[i][j] for j in detour_pos_range) <= 1)
# We can allow more than one insertion
m_insertion.addConstr(gp.quicksum(x_insertion[i][j] for i in v_move_range for j in detour_pos_range) >= 1)
# Calculating of total expected waiting time after adding to the resources of K_hold
for k in K_hold:
m_insertion.addConstr(t_expupdated[k]==exp_pick_comp_time[k] +\
gp.quicksum(x_insertion[i][j]*t_add[i][j]*y_insertion[k][j] for i in v_move_range for j in detour_pos_range))
#Calculating of total expected waiting time after removing from a sequence of K_move
for k in K_move:
m_insertion.addConstr(t_expupdated[k] == exp_pick_comp_time[k] - sum(t_deduct[k][i]*x_insertion[i][j] for i in v_move_range))
#The resources which are not part of K_move or K_hold, exp pick comp time remain unchanged
K_unchanged = list(set([i for i in range (num_cob + num_ded)]) - set(K_hold) -set(K_move))
if len(K_unchanged) != 0:
for k in K_unchanged:
m_insertion.addConstr(t_expupdated[k] == exp_pick_comp_time[k])
#Setting an upper bound for each of the updated expected travel time
for k in range(num_cob + num_ded):
m_insertion.addConstr(z_upbound >= t_expupdated[k])
### IP INSERTION - OPTIMIZATION AND RESULT ###### IP INSERTION - OPTIMIZATION AND RESULT ###### IP INSERTION - OPTIMIZATION AND RESULT ###### IP INSERTION - OPTIMIZATION AND RESULT ###
m_insertion.optimize()
if m_insertion.status == GRB.OPTIMAL:
print(f' updated maximum expected pick completion time: {m_insertion.ObjVal}')
print(f' max pick comp time improvement: {max(exp_pick_comp_time) - m_insertion.ObjVal} seconds')
for i in v_move_range:
for j in detour_pos_range:
if x_insertion[i][j].X > 0.001:
print(f'stopping point {V_move[i]} is inserted into detour position {j} out of {len(t_add[0])} detour positions')
print(f'time added {t_add[i][j]} and deducted {dict_time_reduction_V_move[V_move[i]]}')
print(f'previous exp pick comp time: {exp_pick_comp_time}')
print(f'updated exp pick comp time: {t_expupdated}')
else:
print('no feasible insertion found')In the output section I get the following 2 lines which is the confusing part. It is always the case my model selects the last detour position in the, (here 16 out of 17 as indexing started from 0 to 16 for the 17 detour positions). This is always the case no matter how bad the outcome is, the model is selecting the last detour position. If we look at the t_add matrix, specifically for the stopping point 31 (you can look it up by t_add[-3]), we will see that clearly there are other options which add less time than the current choice of 98.33333333333337. The lowest in the list is 58.333 (t_add[-3][7]) which could have improved both of the objective function even more. Could you please help me understand why it is happening?
stopping point 31 is inserted into detour position 16 out of 17 detour positions time added 98.33333333333337 and deducted 384.68067226890753
1 -
-
-
Hi Joyjit,
You were missing a for-loop in one of your constraint formulations, which caused unintended behavior. Please find the updated constraint formulation below. I highly recommend using gp.quicksum() instead of sum(), like you have done in most of your code, for performance reasons. I, therefore, have also updated your constraint formulation to use gp.quicksum().
# Calculating of total expected waiting time after removing from a sequence of K_move
for k in K_move:
m_insertion.addConstr(
t_expupdated[k] == exp_pick_comp_time[k] -
gp.quicksum(t_deduct[k][i] * x_insertion[i][j] for i in v_move_range for j in detour_pos_range)
)Best regards,
Lennart0 -
-
Hello Lennart,
Thank you for looking into the problem and coming up with a solution. I tried the fix with different variations of input values so that there is no edge cases. The fix seems to work perfectly fine now and the results are making sense.
Thanks again
Joyjit Bhowmick
0 -
Please sign in to leave a comment.
Comments
4 comments