[SCIP] No branching on solving NLP (number of nodes remains eq. to 1)
Vladimir V. Voloshinov
vladimir.voloshinov at gmail.com
Thu Oct 10 01:03:16 CEST 2019
Dear Benjamin,
your recommendation to try "separating/minefficacy* is very helpful, but
the next questions appeared.
Step by step.
1. When I used settings
separating/minefficacyroot = 5000
separating/minefficacy = 0.01
My SCIPAMPL solved the problem in ~400 sec in the root node also.
See the last line of log:
==============================================================
397s| 1 | 0 | 4204k| - | 43M| 0 | - | 427 | 438 | 427
|2664 |8377 | 0 | 0 | 1.615240e-01 | 1.615240e-01 | 0.00%
==============================================================
I used desktop with i7-6700 CPU @ 3.40GHz, SCIP 6.0.2, Ubuntu 16.04.06, GCC
v. 5.4.0 (20160609).
But I have the following questions.
1.1. You wrote "I also disabled heuristics ...".
But how did you do that? I can not find proper settings... :o(
May be it is the reason of that "my" final number of cuts (8377) is twice
bigger than "yours" (3902)?
1.2. Is it possible to reduce the number of annoying "every second" log
lines? For the current running it is about 700 Kb!
Before, we used [display/freq] to reduce log file size, but in this case
number of nodes does not change!
1.3. And still, is possible to force branching for this problems somehow ?
And now BAD news and question.
2. Is it possible that the result of deterministic SCIP-code is hardware
dependent ?
The thing is that we could not reproduce successful solving on another
computers with the same: OS (Ubuntu 16.04.06), GCC and SCIP version
(including Ipopt version)!
All SCIP settings were same as for desktop running!
There were two notebooks: one(CPU i5-8250U @ 1.6Ghz (max 3.4Ghz) and
Virtualbox 6.0.10 on another iMac notebook.
On both machines SCIP fell in stuck like it was before your advice to try
"minefficacy" options.
Number of cuts did not grows dramatically and according to "perf top" tool
SCIP "fall in SoPlex" (on Virtualbox):
==============================================================
Samples: 105K of event 'cpu-clock', Event count (approx.): 7318241336
Overhead Shared Object Symbol
17.60% scip-6.0.2.linux.x86_64.gnu.opt.spx2.none [.]
soplex::SPxDevexPR::selectEnterDenseCoDim
14.94% scip-6.0.2.linux.x86_64.gnu.opt.spx2.none [.]
soplex::CLUFactor::vSolveUright
10.00% scip-6.0.2.linux.x86_64.gnu.opt.spx2.none [.]
soplex::SPxSolver::setupPupdate
...........................
==============================================================
Moreover, I copied /usr/local/bin/scipampl executable (ONLY, and I did not
copy all related libraries) from notebook to desktop.
Linux diff told that this SCIPAMPL file differs from the "native" one that
has been compiled on desktop computer.
But when I ran this "guest" SCIPAMPL on desktop computer the problem has
been solved successfully (as the "native" SCIPAMPL did before)!
Best regards and thanks,
Vladimir.
On Tue, Oct 8, 2019 at 11:26 PM Benjamin Müller <benjamin.mueller at zib.de>
wrote:
> Dear Vladimir,
>
> good news, I configured SCIP in a way that I could solve your problem to
> global optimality:
>
> 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 %
>
> The way how SCIP enforces nonconvex nonlinear constraints is not working
> well for this instance. SCIP will always prioritize separation over
> branching when enforcing nonconvex nonlinear constraints. The only
> condition here is that the computed cuts have a efficacy above some
> threshold. Surprisingly, SCIP finds an insane number of cuts during the
> enforcement rounds and thus SCIP will spend a pretty long time in the root
> node. To overcome this problem, I increased the minimum efficacy
> drastically, i.e.,
> set separating minefficacyroot 5000. As a result, the problem is solved
> after 732 seconds in the root node. I also disabled heuristics and used the
> solution that you sent me.
>
> Yes, you can just write "display statistics" in the interactive shell. You
> can also terminate the current solving process by CTRL+C and then display
> the statistics. I don't really know what you mean with "... not any
> appropriate settings might be inserted in *.set file", but displaying the
> statistics doesn't depend on the settings.
>
> Best,
> Benjamin
>
>
> Am 08.10.19 um 19:39 schrieb Vladimir V. Voloshinov:
>
> Dear Benjamin,
> thank you for your reply!
>
> 1.
> I attached problem's data in CIP format [tmpabc0007_0000start-bound.cip].
> Just in case I attached initial solution also [
> tmpabc0007_0000start.cip.init.sol]. Objective value had been changed form 0
> to "correct" value manually...
>
> 2. You wrote "print statistics ..."
> Am I right that it is possible by SCIP console command "display
> statistics" only, and there is not any appropriate settings might be
> inserted in *.set file ?
>
> Best regards,
> Vladimir
>
> On Tue, Oct 8, 2019 at 2:40 PM Benjamin Müller <benjamin.mueller at zib.de>
> 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
>>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191010/87d5df6d/attachment.html>
More information about the Scip
mailing list