[SCIP] No branching on solving NLP (number of nodes remains eq. to 1)

[Benjamin Müller]

Dear SCIP users,

I was looking at Vladimir's instance and I want to share my insights 
with the mailing list.

The most important thing to notice is the way how SCIP enforces 
nonconvex nonlinear constraints. SCIP will always prefer separation over 
spatial branching when enforcing nonlinear constraints. The only 
requirement is that the cuts must have an efficacy above a threshold 
that is defined by the parameters separating/minefficacy and 
separation/minefficacyroot.

For Vladimir's instance, SCIP finds a huge number of (slightly) violated 
cuts during the enforcement of the LP solution in the quadratic 
constraint handler. Since the problem is purely continuous, no integer 
branching happens and thus SCIP spends a lot of time in generating cuts 
in the root node.

However, after tuning separation/minefficacyroot a bit, I could solve 
the instance in the root node:

   732s|     1 |     0 |  2043k|     - |7712k|   0 |   - | 427 | 438 | 
427 |1522 |3902 |   0 |   0 | 1.615240e-01 | 1.615240e-01 |   0.00%

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 732.03
Solving Nodes      : 1
Primal Bound       : +1.61523993625945e-01 (1 solutions)
Dual Bound         : +1.61523993625945e-01
Gap                : 0.00 %

Take away message: You might want to have a look at the parameters in 
separation/* if you face a similar issue when solving nonconvex MINLPs/NLPs.

Best,
Benjamin

On 10/8/19 1:40 PM, Benjamin Müller wrote:
> Dear Vladimir,
> 
> yes, SCIP did not start to branch yet. Due to the large number of 
> generated cutting planes, I would suspect that most of the time is spent 
> in solving the LP relaxations, but it could also be that some plugins 
> are too expensive. You could print the statistics and check which 
> plugins could be disabled/configured to improve SCIP's performance.
> 
> Could you send me your instance in the CIP format? Then I could have a 
> look at your instance.
> 
> Best regards,
> Benjamin
> 
> On 10/8/19 10:11 AM, Vladimir V. Voloshinov wrote:
>> Dear SCIP developers,
>> we tried to solve some "middle-size" nonlinear problem with polynomial 
>> functions in constraints with out any discrete variables (extr. from 
>> NL-file header below)
>>   430 442 1 0 401 # vars, constraints, objectives, ranges, eqns
>>   199 1 0 0 0 0      # nonlinear constrs, objs; ccons: lin, nonlin, 
>> nd, nzlb
>>   129 221 26         # nonlinear vars in constraints, objectives, both
>>    0 0 0 0 0             # discrete variables: binary, integer, 
>> nonlinear (b,c,o)
>> Some of nonlinear constraints are non-convex quadratic and others (100 
>> totally) are 3rd order polynomial, i.e. sums of the items like " 
>> <var1>*sqr(<var2>)"  (in CIP format).
>> Local solver IPOPT founds local optimum (we suspect that it is global) 
>> in 10 seconds.
>> But SCIP with default settings (and FiberSCIP) can not prove global 
>> optimality in an hours and I DO NOT SEE ANY BRANCHING (domain 
>> decomposition), see fragment of SCIP-log:
>> =============================
>>   time | node  | left  |LP iter    |LP it/n| mem |mdpt |frac |vars 
>> |cons |cols |rows |cuts   | ,,, | dualbound       | primalbound  |  gap
>>   5004s|     1 |     0   | 12932k|     -      |  77M|   0     |   0  | 
>> 427 | 438 | 427 |  89k | 190k | ... |-2.167723e-01 | 1.615240e-01 |   
>>  Inf
>> ...........
>>    358m|     1 |     0   | 31028k|     -     | 103M|   0    |   0   | 
>> 427 | 438 | 427 | 126k| 259k| ...  |-1.800902e-01 | 1.615240e-01 |    Inf
>> SCIP Status        : solving was interrupted [user interrupt]
>> Solving Time (sec) : 21469.69
>> Solving Nodes      : 1
>> Primal Bound       : +1.61523993625950e-01 (2 solutions)
>> Dual Bound         : -1.80090245701914e-01
>> =============================
>>
>> I understand that it is a hard problem, but it is strange that solver 
>> did not try to split bounded domain ! Only number of linear cuts has 
>> been increasing...
>> It looks like SCIP only tries to approximate objective function 
>> epigraph by polyhedron (as a result lower bound increases slowly).
>>
>> Is it normal behaviour of SCIP or some settings for branching rules 
>> may be applied ?
>>
>> Sincerely yours,
>> -- 
>> Vladimir V. Voloshinov,
>> Ph.D, head of lab. C-3 "Distributed computing algorithms", 
>> http://www.iitp.ru/ru/researchlabs/1040.htm,
>> Center for Distributed Computing, Institute for Information 
>> Transmission Problems RAS, http://www.iitp.ru
>> web: our site is temporarily offline 
>> <https://scholar.google.ru/citations?hl=en&user=-m4QhNEAAAAJ&view_op=list_works&sortby=pubdate> 
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://listserv.zib.de/mailman/listinfo/scip
>>
> 

-- 
______________________________
Benjamin Müller
Zuse Institute Berlin
Takustr. 7, 14195 Berlin
benjamin.mueller at zib.de
+49 30 841 85-195