[SCIP] A couple of questions about heuristics and management of the B&B tree...

[Stefan Vigerske]

Hi,

On 12/20/18 1:46 PM, Emiliano Traversi wrote:
> Hi,
> 
> I am using SCIP to solve a  (quite complex apparently) MINLP, it's a
> knapsack problem with a really complex objective function (an example is
> attached, just in case). For this reason I would like to use SCIP mainly as
> heuristic.
> 
> I looked at the documentation and here :
> 
> https://scip.zib.de/doc/html/PARAMETERS.php
> 
> and I tried to fix some of them but I admit I felt a little bit overwhelmed
> by all the parameters :-).
> 
> For this reason, I would like to ask you the following questions:
> 
>   1 - Is it possible to set the frequency of all the heuristics as much
> aggressive as possible, do you have a single parameters to do so? If not,
> which heuristic do you recommend for my problem?

There is a command to set primal heuristic parameters to "aggressive", 
which means, among other things, to increase the frequency of most 
heuristics and enable previously disabled heuristics.
In the SCIP interactive shell, you do this by calling "set heuristics 
emphasis aggressive". This will also output all parameters that has been 
changed, so you can copy this into your settings files. There is also a 
call in the C API to call out to emphasis settings.

I presume that the difficulty in your problem is the continuous 
nonlinear part. Thus, you might want to manually adjust parameters of 
heuristics that work on this part. These heuristics are multistart, 
mpec, subnlp, and undercover (mainly useful if there are products).
Try parameters like heuristics/multistart/onlynlps = FALSE, 
heuristics/subnlp/runalways = TRUE, heuristics/undercover/fixingalts = 
'nli', and setting the freq for all of them to a small number.
Large-neighborhood-search heuristics in SCIP (those whose 
single-letter-abbreviation is a capital letter) other than undercover 
also work for MINLPs, but mainly focus on restricting the search space 
for the binary variables.

> 1bis: Can you explain how exactly the parameters
> priority - freq - freqofs
> work/interact?

Priority decides the order in which a set of heuristics is called at a 
point when heuristics are called.
freq, freqofs, and a hardcoded timing decides about which heuristics to 
include into such a set at a specific point in SCIP. In short, a primal 
heuristic is called in nodes at depth freqofs+x*freq, x a natural 
number. See https://scip.zib.de/doc-6.0.0/html/HEUR.php for a detailed 
documentation.

> 2 - is it possible to limit the size of the B&B tree? I saw
> limits/memory
> but if this limit is exceeded, the process is terminated. Do you have just
> a limit on all the open nodes. Probably this can indirectly achieved by
> imposing to use a diving at some point but what king of diving? And how
> exactly?

There is a memory saving mode. When SCIP's internal count on memory 
usage reaches 80% of limits/memory, then it changes the node selection 
strategy to DFS. The 80% can be changed via memory/savefac. The node 
selection strategy to be chosen by nodeselection/*/memsavepriority.


We have some code in development that does better in handling these 
y*log(y) terms. It still needs some tweaking to also do better on 
(y+0.003)*log(y+0.003), though, but with default settings, after half an 
hour, I'm at 34% gap and a primal bound close to 4.

Best,
Stefan

> I hope the questions are clear. Thanks in any case for the great job you
> did!
> 
> Best regards,
> 
> Emiliano Traversi
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>