Seemingly long optimisation times
OpenHi!
I am solving a TSP for pickup and delivery and delivery only. However, for my intended implementation the solving speed is too slow, is there anything I can do to increase the solving speed?
This is my code:
# --- Model
m = gurobi.Model("SPDP")
if agent.model.time != 67:
m.setParam("OutputFlag", 0)
# m.setParam('TimeLimit', 1)
m.setParam("MIPFocus", 1)
m.setParam("Heuristics", 0.5)
# --- Decision Variables
# xij: 1 if node i and j are connected , i!=n+n+1, j!=0
X = [
[
m.addVar(vtype=gurobi.GRB.BINARY, name="X_" + str(i) + "_" + str(j))
for j in range(1, n + n + k + 2)
if j != i and (i, j) != (0, 2 * n + k + 1)
]
for i in range(n + n + k + 1)
]
X_names = [
[(i, j) for j in range(1, n + n + k + 2) if j != i and (i, j) != (0, 2 * n + k + 1)]
for i in range(n + n + k + 1)
]
# Qi: load on the truck after each node
Q = [
m.addVar(vtype=gurobi.GRB.CONTINUOUS, name="Q_" + str(i))
for i in range(n + n + k + 2)
]
# Bi: beginning time of service at node i
B = [
m.addVar(vtype=gurobi.GRB.INTEGER, name="B_" + str(i)) for i in range(n + n + k + 2)
]
m.update()
# --- Objective Function
if bidding_rule == "makespan":
m.setObjective((B[-1] - B[0]), gurobi.GRB.MINIMIZE)
elif bidding_rule == "travel_time":
m.setObjective(
sum(
X[i][j] * information_arcs[X_names[i][j]]["time"]
for i in range(n + n + k + 1)
for j in range(n + n + k)
if i != j
),
gurobi.GRB.MINIMIZE,
)
elif bidding_rule == "cost":
m.setObjective(
sum(
X[i][j] * information_arcs[X_names[i][j]]["cost"]
for i in range(n + n + k + 1)
for j in range(n + n + k)
if i != j
),
gurobi.GRB.MINIMIZE,
)
# --- Constraints
# Constraint (1): for each destination in the vertices (except 0), there must be an arc going towards it
for j in V:
if j == 0:
continue
m.addConstr(
sum(
X[i][X_names[i].index((i, j))]
for i in range(2 * n + k + 1)
if i != j and (i, j) != (0, 2 * n + k + 1)
)
== 1,
name="Visit every node",
)
# Constraint (2): for each destination in the vertices (except n + n + 1), there must be an arc going from it
for i in V:
if i == n + n + k + 1:
continue
m.addConstr(sum(X[i][j] for j in range(2 * n + k)) == 1, name="Visit every node")
# Constraint (3): updates load after each node visit
for arc in arcs:
m.addConstr(
Q[arc[1]]
>= (Q[arc[0]] + information_vertices[arc[1]]["mass"])
* X[arc[0]][X_names[arc[0]].index((arc[0], arc[1]))],
name="mass update",
)
# Constraint (4): ensures that vehicle capacity is not exceeded
for node in V:
m.addConstr(max(0, information_vertices[node]["mass"]) <= Q[node], name="capacity")
m.addConstr(
Q[node]
<= min(
agent.mass_capacity,
agent.mass_capacity - information_vertices[node]["mass"],
),
name="capacity",
)
# Constraint (5): visit pickup vertex before delivery vertex
for node in P:
m.addConstr(B[node] <= B[node + n], name="precedence")
# Constraint (6): Make sure that next visiting time follows time rules
for arc in A:
if information_arcs[arc]["distance"] == 0:
# Must be at least 1 to prevent subtours
TAT = 1
else:
TAT = agent.TAT / 60
m.addConstr(
B[arc[1]]
>= (B[arc[0]] + information_arcs[arc]["time"] + TAT)
* X[arc[0]][X_names[arc[0]].index((arc[0], arc[1]))],
name="time update",
)
# Constraint (8):
for node in V:
m.addConstr(B[node] <= information_vertices[node]["deadline"], name="deadlines")
# Constraint (9): Vehicle should be empty after performing all requests
m.addConstr(Q[n + n + k + 1] == 0, name="empty at the end")
# Constraint (10): Bounds for B and Q
for node in V:
m.addConstr(B[node] <= 1440, name="bounds")
m.addConstr(Q[node] <= 3000, name="bounds")
m.update()
start = time.time()
m.optimize()
end = time.time()
opt_time = end - start
print(opt_time)
And this is a log file for an instance that is taking particularly long.
Set parameter MIPFocus to value 1
Set parameter Heuristics to value 0.5
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)
CPU model: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 110 rows, 212 columns and 452 nonzeros
Model fingerprint: 0x2b28c196
Model has 364 quadratic constraints
Variable types: 15 continuous, 197 integer (182 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
QMatrix range [1e+00, 1e+00]
QLMatrix range [1e+00, 3e+01]
Objective range [1e+00, 4e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 3e+03]
Presolve removed 17 rows and 10 columns
Presolve time: 0.00s
Presolved: 667 rows, 489 columns, 2335 nonzeros
Variable types: 167 continuous, 322 integer (174 binary)
Root relaxation: objective 0.000000e+00, 63 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 47 - 0.00000 - - 0s
0 0 0.00000 0 63 - 0.00000 - - 0s
0 0 0.00000 0 75 - 0.00000 - - 0s
0 0 0.00000 0 23 - 0.00000 - - 0s
H 0 0 9.6000000 0.00000 100% - 0s
0 0 0.00000 0 31 9.60000 0.00000 100% - 0s
0 0 0.00000 0 42 9.60000 0.00000 100% - 0s
0 0 0.00000 0 53 9.60000 0.00000 100% - 0s
H 0 0 4.4000000 0.00000 100% - 0s
0 0 0.00000 0 56 4.40000 0.00000 100% - 0s
0 0 0.00000 0 58 4.40000 0.00000 100% - 0s
0 0 0.00000 0 65 4.40000 0.00000 100% - 0s
0 2 0.00000 0 47 4.40000 0.00000 100% - 0s
* 2566 1026 34 2.4000000 0.00000 100% 9.5 2s
Cutting planes:
Learned: 14
Gomory: 1
Implied bound: 12
Clique: 3
MIR: 23
StrongCG: 5
Flow cover: 49
Inf proof: 1
Mod-K: 1
RLT: 3
Relax-and-lift: 16
Explored 3405 nodes (33383 simplex iterations) in 4.02 seconds (2.22 work units)
Thread count was 8 (of 8 available processors)
Solution count 3: 2.4 4.4 9.6
Optimal solution found (tolerance 1.00e-04)
Best objective 2.400000000000e+00, best bound 2.400000000000e+00, gap 0.0000%
Could you help me out? Thank you in advance!
Kind regards,
Nikki Kamphuis
0
-
Hi,
Have you tried default parameters?
Or the NoRel heuristic (e.g. set \(\texttt{NoRelHeurTime}\) to 1)?Maybe also reformulating the constraints.
Cheers,
David0 -
Hi,
Thank you for answering so quickly! I tried both, but the effect on the solution time is almost none.Regards,
Nikki
0
Please sign in to leave a comment.
Comments
2 comments