[SCIP] "Resolve instable" in SCIP statistics?

Sun Dec 20 14:03:19 CET 2020

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20201220/f6c3ef89/attachment.html>