[SCIP] Settings for large continuous bilinear problem

[Stefan Vigerske]

Hi,

proving optimality on such geometric problems is very hard for spatial 
branch-and-bound based solvers due to the inherent nonconvexity of the 
problem. Also with other solvers (ANTIGONE, BARON), I saw that proving 
optimality for some kissing number problems can take a while.

The first attempt for saving memory in SCIP is usually to switch the 
node-selection rule to depth-first-search, e.g., by setting
   nodeselection/dfs/stdpriority = 1000000
If you set a memory limit for SCIP (limits/memory), then SCIP will also 
switch the nodeselection to DFS if the memory usage reaches 80% 
(memory/savefac) of the limit.

The high memory usage for these kind of problems is usually caused by 
the many local cuts that are generated by SCIP and stored in the nodes. 
It's probably not so easy to reduce the amount of generated cuts, but 
you could play with the options constraints/quadratic/sepafreq, 
constraints/quadratic/minefficacysepa, and 
constraints/quadratic/minefficacyenfofac.

Other options that might influence performance are 
constraints/quadratic/disaggregate and separating/eccuts/{freq,...}.
If finding feasible solutions becomes difficult, then try to make the 
multistart heuristic run more intensively 
(heuristics/multistart/{freq,...}).

Also check whether you see any possibility to tighten the bounds on your 
variables.

Hope that helps,
Stefan

On 08/02/2017 12:43 PM, Vladimir V. Voloshinov wrote:
> Dear all,
> In combinatorial geometry there is known so called "Spherical Code
> problem" AKA "Tammes problem",
> https://en.wikipedia.org/wiki/Spherical_code,
> http://neilsloane.com/packings.
> The problem may be posed as continuous bilinear non-convex Math.
> Progr. problem (I used Pyomo to generate AMPL-stub).
> I tried to solve it by SCIP 4.0.0 for 3D space up to 14 points (to be
> located on 3D-Sphere to maximize minimal "pairwise" distance)
> After a number of runs I've seen that SCIP almost at the beginning
> finds actually optimal solution and spends all remaining time to prove
> its optimality.
> 
> But memory became limiting resource here.
> Even for 8 3d-points, limit of 28Gb have been exhausted  with gap from
> 90% till 240% (depending of initial feasible solution, which I put
> into AMPL-stub).
> 
> Can you recommend any SCIP-options to save memory usage, of course, at
> the expense of longer running time?
> May be autorestart options may be applied somehow? (I had tried once
> but got invariable "dualbound" and killed the process after a long
> time).
> 
> And one more questions: can you recommend any surveys/reports/articles
> devoted to SCIP application for continuous global optimization
> (bilinear)?
> 
> Sincerely yours,
> Vladimir V. Voloshinov.
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
> 


-- 
http://www.gams.com/~stefan