[Scip] enabling local branching

[Tobias Achterberg]

Hi Sandor,

you can change settings by modifying the "scip.set" file or by setting
the options directly in the SCIP shell with the "set ..." command.
>From the SCIP shell, you can save all options with "set save
<filename.set>" or save only the non-default options with "set diff
<filename.set>". They can be loaded with "set load <filename.set>".

To activate local branching, you need to change the value of the
parameter "heuristics/localbranching/freq". I would recommend to set
this calling frequency to 20 or 30 (lower value means that the
heuristic is called more often).
In the SCIP shell, you can type "set heur local freq 30" to set this
value. If you only type "set heur local", you will get a list of
parameters controlling the local branching heuristic. If you have
questions about the meaning of the parameters, feel free to ask.

Note that local branching in SCIP is implemented as a primal
heuristic, which is slightly different than to the idea proposed in
the original paper of Fischetti and Lodi. They use local branching to
split the problem into two separate parts, namely the points close to
the current incumbent and the points far away. The region close to the
incumbent is processed first, and if this results in an improved
solution, a corresponding branching is introduced to the "far away"
region. This approach to use the concept as a branching rule leads to
the introduction of very dense inequalities, which range over all
integer variables. This can destroy the stability of the LP
relaxations and slow down the LP solving process. Therefore, we
decided to only use local branching as a heuristic, which means to
search in the "close to incumbent" region for better solutions but
abort the search if it takes too long (in terms of branching nodes
needed for the sub-MIP). The "far away" constraint is not added to the
problem, even if the "close to incumbent" subproblem was solved
completely.


In our experiments, we got the impression that local branching is
inferior to RINS, which is a different large neighborhood search
improvement heuristic due to Danna, Rothberg, and Le Pape. You
probably should try this heuristic instead, or use both of them.


If you like (and are allowed), you could send me your MIP model as MPS
or LP file and I try to figure out some good parameter settings. Of
course, this should not go to the SCIP list but to me personally.


Best regards,  Tobias


Sandor Balogh wrote:
> Dear All,
> 
> I would like to solve a very difficult scheduling problem.
> 
> It is almost sure that the best strategy would be to emphasise
> feasibility when branching during the early stage of the calculation.
> (The default settings seem to be OK, it is not necessary to change
> them.)
> 
> If a feasible solution is found then improve that solution with local branching.
> 
> Which lines should i change in the file scip.set to enable local
> branching for this purpose?
> 
> Thanks in advance,
> 
> Sandor Balogh
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-- 
Tobias Achterberg          Konrad-Zuse-Zentrum fuer
                           Informationstechnik Berlin
Tel: +49 (0)30 84185-301   Takustr. 7
Email: achterberg at zib.de   D-14195 Berlin, Germany