[Scip] explanation of use of primal heuristics

Timo Berthold berthold at zib.de
Tue Feb 19 19:36:08 MET 2013


Hi Victor,

some add-ons to what Gregor said:
Sounds like you are looking for
set heuristics emphasis fast which disables expensive heuristics
(diving+LNS), but keeps the cheap ones.
In particular diving heuristics might also find conflict constraints which
might be helpful for guiding the remaining search.

The circumstance that seemingly effectless changes cause a big difference
in running time, is called performance variability. If you are interested
in this, look at the MIPLIB2010 paper, there is a section discussing this
issue. Let me tell you that all MIP solvers that I am aware of suffer from
this.

Just a general not on solver tuning: up to my experience, it is much
better to invetigate what works good for your problems than what does not
work out. The latter can save you some percent of running time (in your
example, coefdiving took 3% of the overall running time), the former can
really make the difference

So or so: it is some kind of gambling.

Good luck
Timo

> Hi Victor,
>
> your last sentence stresses the fact that our testing has not been that
> bad :)
>
> The order in which heuristics are called is not determined by their
> priority alone, but also by their heuristic timing (before/after a node,
> before presolve, to mention only a few). Some heuristics as, e.g.,
> feasibility pump, have a threshold on the number of already found
> solutions and will not be run if this threshold is exceeded.
> The execution of SCIP heuristics can have side effects on the overall
> search-performance of the solver due to the variable statistics
> collected, which is why even a fruitless call of a heuristic can still
> speed up the solution process.
>
> If you are interested in disabling all heuristics at once, you can
> simply type
>
> set heuristics emphasis off
>
> in the SCIP interactive shell.
>
> Best regards
> gregor
>
> Am 19.02.2013 18:57, schrieb Victor Miller:
>> I have a number of IP problems which I'm using SCIP to solve.  I've
>> noticed that in these problems that the various diving heuristics
>> *never* find a solution.  So I started experimenting with disabling
>> them, and the running time went up!  I have one small case which takes
>> Scip 2.97 seconds to solve on my workstation.  I noticed that
>> coefdiving took 0.11 seconds but found no solutions, so I disabled
>> it.  Much to my surprise that caused the solution time to double!  By
>> disabling it, it allowed other fruitless heuristics to run such as
>> pscostdiving. But when I disabled those, others now came into play.
>> I'm not completely clear on how heuristics are chosen to be run.  I
>> would think that it's first by priority, but what happens if a
>> heuristic reports that it didn't find a solution?  So far, it's been
>> like whack-a-mole.  I disable a bunch of heuristics which don't find
>> solutions, and another new one pops up.  So far, not disabling any
>> heuristics gives the lowest run time.
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>



More information about the Scip mailing list