User MIP start in Gurobi logs
回答済み
When I set an initial solution before solving a Gurobi model, I see one of the following three different kind of output inside Gurobi logs.
Case A
Warning: Completing partial solution with 30107 unfixed non-continuous variables out of 30210
User MIP start did not produce a new incumbent solution
Case B
User MIP start did not produce a new incumbent solution
User MIP start violates constraint <CONSTR_NAME> by 1.000000000
Case C
User MIP start did not produce a new incumbent solution
Case A and B make total sense (either I am not loading all variable values or my solution is not feasbiel). What does Case C means? Does it mean that my solution is feasible, but the solver already found a solution that is at least as good as mine?
Full log of case C (in this case the solution I provide has value 247, hence it is already optimal):
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: Intel(R) Xeon(R) Gold 6140M CPU @ 2.30GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 16 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 37832 rows, 30211 columns and 1748296 nonzeros
Model fingerprint: 0x99e137bf
Model has 314 general constraints
Variable types: 1 continuous, 30210 integer (30210 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+02]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 4e+01]
User MIP start did not produce a new incumbent solution
Presolve removed 7546 rows and 5953 columns (presolve time = 5s) ...
Presolve removed 31305 rows and 6026 columns (presolve time = 10s) ...
Presolve removed 30763 rows and 6039 columns
Presolve time: 11.56s
Presolved: 7069 rows, 24172 columns, 1237310 nonzeros
Variable types: 0 continuous, 24172 integer (24167 binary)
Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Root barrier log...
Ordering time: 0.05s
Barrier statistics:
AA' NZ : 1.927e+06
Factor NZ : 4.830e+06 (roughly 50 MB of memory)
Factor Ops : 6.051e+09 (less than 1 second per iteration)
Threads : 13
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 2.47000000e+02 1.32800000e+02 4.43e+03 0.00e+00 4.36e-01 15s
1 2.47000000e+02 1.26624747e+02 2.13e+03 1.72e-02 2.00e-01 15s
2 2.47000000e+02 1.51099807e+02 7.09e+02 2.67e-03 6.53e-02 15s
3 2.47000000e+02 1.99289481e+02 1.15e+02 7.56e-16 1.10e-02 15s
4 2.47000000e+02 2.20472788e+02 2.46e+01 5.62e-16 2.61e-03 16s
5 2.47000000e+02 2.31943755e+02 3.94e+00 1.53e-16 6.20e-04 16s
Barrier performed 5 iterations in 15.64 seconds (14.51 work units)
Barrier solve interrupted - model solved by another algorithm
Concurrent spin time: 0.38s (can be avoided by choosing Method=3)
Solved with dual simplex
Root relaxation: objective 2.470000e+02, 1824 iterations, 1.53 seconds (1.22 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
H 0 0 247.0000000 247.00000 0.00% - 16s
0 0 247.00000 0 132 247.00000 247.00000 0.00% - 16s
Explored 1 nodes (3449 simplex iterations) in 16.35 seconds (15.01 work units)
Thread count was 16 (of 16 available processors)
Solution count 1: 247
Optimal solution found (tolerance 1.00e-04)
Best objective 2.470000000000e+02, best bound 2.470000000000e+02, gap 0.0000%
User-callback calls 1578, time in user-callback 0.16 sec
Gurobi completed with status code 2 (OPTIMAL)
-
Case C means that the MIP Start algorithm run into either an internal time limit or it reached the StartNodeLimit value. You could try increasing the StartNodeLimit parameter value to allow more iterations for the MIP Start optimization. Please note that Case A and Case B could run into the same issue. In Case A, when you provide only a partial MIP Start, then Gurobi uses only the provided MIP Start values and leaves all other variables in their given bounds. Then it runs a MIP Start optimization problem which may run into the StartNodeLimit. In Case B, Gurobi will try to relax some MIP Start values to hopefully somehow "repair" the MIP Start solution. If this is successful, then it is still possible for the MIP Start optimization problem to run into the StartNodeLimit.
Best regards,
Jaromił0 -
Thank you Jaromił, I still have to try changing the settings you suggested, but there is something not clear to me: suppose that I am setting a MIPStart value for each variable in my the model (I still need to double check, but let assume it), then I should either "immediately" see something as in Case B or it would mean that my solution is feasible (although for some reason Gurobi does not use it and does not print its value on the screen)? Are there other possibilities?
0 -
Found the issue: it seems that Gurobi does not always emit a message in Case B, even if the solution I load is not feasible. I found a bug in the heuristic procedure I use and now Gurobi immediatly load my initial solution (with the same objective value I expect).
Thank you for your help!
0
サインインしてコメントを残してください。
コメント
3件のコメント