Warm start approach gives suboptimal solution
ユーザーの入力を待っています。
Hi,
I use a warm-start approach to solving MIP problems because Gurobi takes too long to solve them if I don't provide an initial feasible solution.
The problem is that the results of the warm-start method with and without the start option are different. Here are the logs of the two methods. (Note that I haven't changed the MIPGap parameter)
With start:
Gurobi 10.0.1 (win64) logging started Fri Apr 7 10:34:48 2023
Set parameter FuncMaxVal to value 1e+100
Set parameter NumericFocus to value 3
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 6512 rows, 10080 columns and 21378 nonzeros
Model fingerprint: 0x57a3161d
Model has 4788 general constraints
Variable types: 10080 continuous, 0 integer (0 binary)
Coefficient statistics:
Matrix range [1e-03, 1e+04]
Objective range [7e+01, 7e+04]
Bounds range [1e+05, 7e+06]
RHS range [6e+00, 7e+03]
PWLCon x range [1e-03, 7e+06]
PWLCon y range [6e-06, 3e+05]
User MIP start produced solution with objective 3.06974e+10 (0.04s)
Loaded user MIP start with objective 3.06974e+10
Presolve added 3594 rows and 4372 columns
Presolve time: 0.99s
Presolved: 10106 rows, 14452 columns, 36845 nonzeros
Presolved model has 2364 SOS constraint(s)
Variable types: 13873 continuous, 579 integer (579 binary)
Root relaxation: objective 2.912494e+10, 4964 iterations, 0.89 seconds (0.12 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 2.9125e+10 0 96 3.0697e+10 2.9125e+10 5.12% - 2s
0 0 2.9671e+10 0 83 3.0697e+10 2.9671e+10 3.34% - 4s
0 0 2.9675e+10 0 84 3.0697e+10 2.9675e+10 3.33% - 4s
0 2 2.9675e+10 0 83 3.0697e+10 2.9675e+10 3.33% - 5s
379 344 2.9967e+10 49 71 3.0697e+10 2.9896e+10 2.61% 34.0 10s
Cutting planes:
Implied bound: 48
Explored 533 nodes (30023 simplex iterations) in 11.41 seconds (2.86 work units)
Thread count was 8 (of 8 available processors)
Solution count 1: 3.06974e+10
Optimal solution found (tolerance 1.00e-04)
Best objective 3.069739716435e+10, best bound 3.069739716435e+10, gap 0.0000%
Solution quality statistics for model Extended Gurobi Bilinear Model :
Maximum violation:
Bound : 0.00000000e+00
Constraint : 1.00029865e-07 (Constr1_1)
Integrality : 0.00000000e+00
Without Start (still running):
Set parameter FuncMaxVal to value 1e+100
Set parameter NumericFocus to value 3
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 6512 rows, 10080 columns and 21378 nonzeros
Model fingerprint: 0x558555fa
Model has 4788 general constraints
Variable types: 10080 continuous, 0 integer (0 binary)
Coefficient statistics:
Matrix range [1e-03, 1e+04]
Objective range [7e+01, 7e+04]
Bounds range [1e+05, 7e+06]
RHS range [6e+00, 7e+03]
PWLCon x range [1e-03, 7e+06]
PWLCon y range [6e-06, 3e+05]
Presolve added 3594 rows and 4372 columns
Presolve time: 1.02s
Presolved: 10106 rows, 14452 columns, 36845 nonzeros
Presolved model has 2364 SOS constraint(s)
Variable types: 13873 continuous, 579 integer (579 binary)
Root relaxation: objective 2.899191e+10, 4997 iterations, 0.86 seconds (0.12 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 2.8992e+10 0 95 - 2.8992e+10 - - 2s
0 0 2.9685e+10 0 65 - 2.9685e+10 - - 5s
0 2 2.9685e+10 0 65 - 2.9685e+10 - - 6s
218 210 2.9860e+10 35 60 - 2.9830e+10 - 62.2 10s
665 588 2.9860e+10 67 78 - 2.9830e+10 - 49.0 15s
2082 1787 3.0035e+10 14 71 - 3.0034e+10 - 53.6 40s
2098 1798 3.0038e+10 16 78 - 3.0035e+10 - 53.7 45s
2149 1840 3.0051e+10 22 83 - 3.0035e+10 - 54.3 50s
5040 3356 3.0590e+10 256 88 - 3.0036e+10 - 97.9 366s
17473 13393 3.0767e+10 186 218 - 3.0041e+10 - 107 1124s
72709 57876 3.0684e+10 95 263 - 3.0047e+10 - 108 4035s
104594 82622 3.0645e+10 45 148 - 3.0050e+10 - 104 5094s
*104859 79055 278 3.068752e+10 3.0050e+10 2.08% 104 5094s
105056 79149 3.0640e+10 46 126 3.0688e+10 3.0050e+10 2.08% 104 5107s
105301 79647 3.0279e+10 25 123 3.0688e+10 3.0050e+10 2.08% 104 5120s
....
3571582 2842690 3.0685e+10 58 116 3.0685e+10 3.0521e+10 0.53% 103 269150s
3574019 2842853 cutoff 80 3.0685e+10 3.0521e+10 0.53% 103 269262s
First of all, Gurobi didn't improve the initial feasible solution I provided at all; it just brought the best bound to the same level as the initial feasible solution (which is wrong, as you can see from the logs when solving without the Start option). I noticed that there exist better solutions, and Gurobi finds them only if Gurobi solves the model without the Start option. Why does the warm-start method give a worse value?
Best regards,
Eunseok Kim
-
正式なコメント
-
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 Eunseok Kim,
As you are already using NumericFocus=3 you seem to be aware that your model might suffer from numerical issues. Actually the coefficient ranges are quite large and you should think about scaling to reduce them, see our numerical guidelines. You are using general constraints that are potentially approximated via PWL functions which could also lead to numerical issues.
If you provide a MIP start the solution path of the solver changes and if numerical issues are present actually many (sometimes strange) things can happen.
I can see that the MIP start solution has rather good quality with respect to violations.
What about the better solutions found in the run without MIP start? How does their quality look like?Best regards,
Mario0 -
投稿コメントは受け付けていません。
コメント
2件のコメント