[SCIP] "Resolve instable" in SCIP statistics?

[Marc Pfetsch]

Hi Christian,

the lines

> Warning: unscaled dual violation = 1.07138e-06 and residual = 1.07138e-06
> (node 1) numerical troubles in LP 117 -- solve again with primal
simplex without scaling

indicate the behavior I explained earlier. Gurobi terminates with the
status that the unscaled problem is not feasible (or rather very
slightly infeasible). The SCIP tries to recover.

You can add a call to SCIPlpiWriteLP() in the file lpi_grb.c in function
 SCIPlpiSolveDual() to write out the files.

Best

Marc


On 20/12/2020 14:03, Franzen, Christian wrote:
> Hi Marc.
> 
> 
> I did some further investigation and the log output of Gurobi indicates
> some numerical issues:
> 
> 
> ...
> 
> Gurobi Optimizer version 9.0.2 build v9.0.2rc0
> Optimize a model with 32793 rows, 102025 columns and 2555610 nonzeros
> Coefficient statistics:
>   Matrix range     [1e+00, 2e+03]
>   Objective range  [3e+01, 6e+05]
>   Bounds range     [1e+00, 1e+00]
>   RHS range        [1e+00, 5e+04]
> Iteration    Objective       Primal Inf.    Dual Inf.      Time
>        0    4.3786197e+07   0.000000e+00   1.667889e+04      0s
>     1152    4.3786110e+07   0.000000e+00   0.000000e+00      1s
> 
> Solved in 1152 iterations and 0.90 seconds
> Optimal objective  4.378611043e+07
> Warning: unscaled dual violation = 1.07138e-06 and residual = 1.07138e-06
> (node 1) numerical troubles in LP 117 -- solve again with primal simplex
> without scaling
> ...
> ...
> Gurobi Optimizer version 9.0.2 build v9.0.2rc0
> Optimize a model with 32326 rows, 87534 columns and 2182273 nonzeros
> Coefficient statistics:
>   Matrix range     [1e+00, 2e+03]
>   Objective range  [3e+01, 6e+05]
>   Bounds range     [1e+00, 1e+00]
>   RHS range        [1e+00, 5e+04]
> Iteration    Objective       Primal Inf.    Dual Inf.      Time
>        0    4.4043728e+07   0.000000e+00   4.354066e+04      0s
> Warning: 1 variables dropped from basis
> Warning: switch to quad precision
>     2506    4.4034847e+07   0.000000e+00   1.764252e+04      5s
>     3271    4.4034676e+07   0.000000e+00   0.000000e+00      8s
> 
> Solved in 3271 iterations and 8.15 seconds
> Optimal objective  4.403467558e+07
> ...
> 
> Do I have any chance, to get an LP file of the program with that
> numerical issues? I tried to output the LP file at the end of each
> pricing iteration within my pricer, but that does not output exactly the
> LP that is solved in above examples? Is there anything else I can do to
> figure out the root cause of that issues?
> 
> Regards
> Christian
> 
> ------------------------------------------------------------------------
> *Von:* Scip <scip-bounces at zib.de> im Auftrag von Franzen, Christian
> <franzen at or.rwth-aachen.de>
> *Gesendet:* Sonntag, 20. Dezember 2020 09:58
> *An:* Marc Pfetsch; scip at zib.de
> *Betreff:* Re: [SCIP] "Resolve instable" in SCIP statistics?
>  
> 
> Hi Marc.
> 
> 
> Thanks for your support. I am using Gurobi as LP-solver. Scale of the
> coefficients should be fine, they are all between 1e2 and 1e6, however I
> have some Big-M's in my objective function that I can not get rid of. I
> am wondering why I run into stability issues only when I solve my LP for
> some time (e.g., for a day). It seems to me that after some time my
> pricer generates columns that imply that issues. I will activate LP
> solver logging and see if Gurobi is giving me some hints.
> 
> 
> Regards
> 
> Christian
> 
> 
> 
> ------------------------------------------------------------------------
> *Von:* Scip <scip-bounces at zib.de> im Auftrag von Marc Pfetsch
> <pfetsch at mathematik.tu-darmstadt.de>
> *Gesendet:* Freitag, 18. Dezember 2020 20:58
> *An:* scip at zib.de
> *Betreff:* Re: [SCIP] "Resolve instable" in SCIP statistics?
>  
> 
> 
> Hi Christian,
> 
> the "resolve instable" indeed refers to the work that SCIP and the
> LP-solver try to obtain a numerically correct result. SCIP checks
> whether the solution returned by the solver is actually feasible. If
> this is not the case, then it tries to switch the LP-solver from dual to
> primal, tries to tighten the feasibility tolerance, starts from scratch
> (no warm start) etc.
> 
> In your case, the LP-solver seems to struggle with the LP-relaxation.
> Which solver are you using?
> 
> You can try to improve your model, e.g., by scaling or checking that you
> do not have very large coefficients together with very small ones in
> constraints or the coefficients. You can also check whether you have
> big-Ms in the model that you might be able to reduce. But first should
> probably turn on the output of the LP-solver to maybe get an idea of
> what is going wrong (parameter display/lpinfo).
> 
> Best
> 
> Marc
> 
> 
> 
> On 18/12/2020 13:56, Franzen, Christian wrote:
>> Hi SCIP Team.
>> 
>> 
>> I am implementing a branch-and-price solver and for one of my benchmark
>> instances solving is significantly slower than for other instances. In
>> the statistics of SCIP is see the following output:
>> 
>> 
>> LP                 :       Time      Calls Iterations  Iter/call 
>>  Iter/sec  Time-0-It Calls-0-It    ItLimit
>>   primal LP        :   39822.63       1350   22117847   22431.89   
>>  555.41      80.20        364
>>   dual LP          :     903.64          9     622937   69215.22   
>>  689.36       0.00          0
>>   lex dual LP      :       0.00          0          0       0.00          -
>>   barrier LP       :       0.00          0          0       0.00       
>>   -       0.00          0
>>   resolve instable :   32994.26        583   21004525   36028.34     636.61
>>   diving/probing LP:       8.31         27      28543    1057.15    3436.36
>>   strong branching :       0.00          0          0       0.00       
>>   -          -          -          0
>>     (at root node) :          -          0          0       0.00          -
>>   conflict analysis:       0.00          0          0       0.00          -
>> 
>> I am not sure what these statistics tell me. Most of the time the LP
>> solver is struggeling with resolving any instability. What kind of
>> instability is meant here? Is this something related to numerical
>> issues? What can I do to solve that "issue"?
>> 
>> 
>> Regards
>> 
>> Christian
>> 
>> 
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://listserv.zib.de/mailman/listinfo/scip
>> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip