Why is Gurobi taking so much time to find the optimal solution to objective 2?
ユーザーの入力を待っています。
Hi, I have a question regarding algorithms. I've built a model with a relatively complex expression of objective 1 and a relatively simple expression of objective 2. The codes are as follows (in Python) :
lgtp=slot_allocation.addVars(D,lb=3,ub=3.3,vtype=GRB.CONTINUOUS,name='lgtp')
for d in D:
slot_allocation.addGenConstrLogA(tp[d],lgtp[d],10.0, "FuncPieces=-1 FuncPieceError=1e-6")
tp3=slot_allocation.addVars(D,O_north,lb=30,ub=4000,vtype=GRB.CONTINUOUS, name = "temp3")
for d in D:
for ono in O_north:
slot_allocation.addConstr(gp.quicksum(flightprocedure[m,d]*math.pow(10,0.1*EPNL_alt[m,d,ono])+\
(1-flightprocedure[m,d])*math.pow(10,0.1*EPNL_ori[m,d,ono]) for m in M)/N[d]/100000==tp3[d,ono])
lgtp3=slot_allocation.addVars(D,O,lb=1.4,ub=3.8,vtype=GRB.CONTINUOUS,name='lgtp2')
for d in D:
for ono in O_north:
slot_allocation.addGenConstrLogA(tp3[d,ono],lgtp3[d,ono],10.0, "FuncPieces=-1 FuncPieceError=1e-6")
noise=gp.quicksum(10*(lgtp3[d,ono]+5)+10*lgtp[d]-39.4 for d in D for ono in O_north)
total_displacement = gp.quicksum(abs(t-Tdm[d][m])*flightslot[m,d,t] for d in D for m in M for t in T)
slot_allocation.setObjectiveN(noise,0,2,GRB.MINIMIZE)
slot_allocation.setObjectiveN(total_displacement,1,1,GRB.MINIMIZE)
When Gurobi solves the model, it quickly gets the optimal solution to objective 1. However, it takes such a long time to find the optimal solution to objective 2 with large gap (I set TimeLimit=3600). Why does this happen?
Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (win64)
CPU model: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 95596 rows, 1555757 columns and 14658989 nonzeros
Model fingerprint: 0x5d12a1eb
Model has 14 quadratic constraints
Model has 21 general constraints
Variable types: 63 continuous, 1555694 integer (1555687 binary)
Coefficient statistics:
Matrix range [7e-05, 3e+02]
QMatrix range [1e+00, 1e+00]
Objective range [1e+00, 3e+02]
Bounds range [1e+00, 4e+03]
RHS range [1e+00, 3e+03]
QRHS range [9e+05, 9e+05]
---------------------------------------------------------------------------
Multi-objectives: starting optimization with 2 objectives ...
---------------------------------------------------------------------------
Multi-objectives: applying initial presolve ...
---------------------------------------------------------------------------
Presolve removed 85814 rows and 1481549 columns
Presolve time: 3.35s
Presolved: 9796 rows and 74208 columns
---------------------------------------------------------------------------
Multi-objectives: optimize objective 1 () ...
---------------------------------------------------------------------------
Presolve removed 8470 rows and 64803 columns (presolve time = 6s) ...
Presolve removed 8470 rows and 64815 columns
Presolve time: 5.89s
Presolved: 1328 rows, 9393 columns, 83509 nonzeros
Presolved model has 1 bilinear constraint(s)
Variable types: 452 continuous, 8941 integer (8881 binary)
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 1.0153578e+03 8.959817e+02 0.000000e+00 10s
1099 1.0360908e+03 0.000000e+00 0.000000e+00 10s
Root relaxation: objective 1.036091e+03, 1099 iterations, 0.02 seconds (0.02 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1036.09079 0 25 - 1036.09079 - - 9s
H 0 0 1041.8602860 1036.09079 0.55% - 9s
0 0 1040.94705 0 34 1041.86029 1040.94705 0.09% - 9s
0 0 1041.78509 0 28 1041.86029 1041.78509 0.01% - 9s
Cutting planes:
Gomory: 10
RLT: 1
Explored 1 nodes (1683 simplex iterations) in 9.85 seconds (11.88 work units)
Thread count was 8 (of 8 available processors)
Solution count 1: 1041.86
Optimal solution found (tolerance 1.00e-04)
Best objective 1.041860286020e+03, best bound 1.041785091838e+03, gap 0.0072%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 2 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective 18221
Presolve removed 226 rows and 6054 columns
Presolve time: 0.90s
Presolved: 9585 rows, 68154 columns, 602515 nonzeros
Presolved model has 7 bilinear constraint(s)
Found heuristic solution: objective 18197.000000
Variable types: 3151 continuous, 65003 integer (64581 binary)
Found heuristic solution: objective 10501.000000
Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Root barrier log...
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.089e+05
Factor NZ : 2.413e+05 (roughly 20 MB of memory)
Factor Ops : 8.968e+06 (less than 1 second per iteration)
Threads : 2
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 6.55644408e+07 -5.73662353e+05 6.34e+04 1.32e+01 2.92e+03 11s
Barrier performed 0 iterations in 11.31 seconds (13.81 work units)
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Use crossover to convert LP symmetric solution to basic solution...
Root crossover log...
0 DPushes remaining with DInf 0.0000000e+00 11s
432 PPushes remaining with PInf 0.0000000e+00 11s
0 PPushes remaining with PInf 0.0000000e+00 11s
Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00 11s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
1845 2.0700000e+02 0.000000e+00 0.000000e+00 11s
1845 2.0700000e+02 0.000000e+00 0.000000e+00 11s
Root relaxation: objective 2.070000e+02, 1845 iterations, 0.56 seconds (0.44 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 207.00000 0 118 10501.0000 207.00000 98.0% - 11s
H 0 0 8098.0000000 207.00000 97.4% - 12s
0 0 207.00000 0 137 8098.00000 207.00000 97.4% - 12s
0 0 207.00000 0 137 8098.00000 207.00000 97.4% - 13s
......
Cutting planes:
Gomory: 152
Lift-and-project: 2
MIR: 140
StrongCG: 9
Flow cover: 3
RLT: 3
Explored 96584 nodes (7151677 simplex iterations) in 3600.12 seconds (2662.39 work units)
Thread count was 8 (of 8 available processors)
Solution count 10: 5195 5203 5207 ... 5222
Time limit reached
Best objective 5.195000000000e+03, best bound 5.126000000000e+03, gap 1.3282%
---------------------------------------------------------------------------
Multi-objectives: stopped in 3602.40 seconds (2662.39 work units), solution count 10
Time Limit reached
-
正式なコメント
-
Gurobi Staff
This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi,
Only because some objective function "looks" easier than another one does not mean that it is easier to solve.
For the first objective, the dual bound obtained by the root relaxation is already very near to the optimal value, and an optimal solution has been quickly found by a heuristic (line starting with "H"). So there is no need to start the branching phase.
For the second objective, it is not clear whether the dual bound is weak (far away from the optimal value), or the built-in heuristics cannot easily find better solutions. Therefore, the resulting gap is still large and potentially needs a large branch-and-bound tree to close the gap. Is there some additional output where you currently only have "......"?
Best regards,
Mario0 -
投稿コメントは受け付けていません。
コメント
2件のコメント