[Scip] branching

[michael.winkler@zib.de]

Hi Alessia,

> Hello,
>
> I have some questions/doubts about the branching. I have implemented my
> own branching together with the pricing, in the form of a constraint
> handler, as I don't have any variable to be integer but a constraint
> (equal to the sum of variables with some parameters) to be integer in
> the optimal solution. To do so in the constraint handler I am checking
> if this sum is integer, if yes I end up with *result = SCIP_FEASIBLE, if
> not I create two nodes, add constraints to them and end with *result =
> SCIP_BRANCHED.
>
> The code is working and finding the correct solution, but I was
> wondering if I should also modify some bounds in this process or if
> everything is done automatically by scip? For instance when I found an
> integer solution, should I manually modify the primal or the cut off
> bound? (all of this to eventually speed up the solving).
>

Depending on whether your constraints will be propagated in the child
nodes and this propagation is able to deduce (better) bounds you would
also imprint on your variables, you do not need to change them by
yourself.
Therefore, when creating a constraint you need to set the propagate flag
to TRUE and the corresponding constraint handler needs to have the
CONSPROP callback implemented (, which is done for all existing SCIP
constraint handlers.)
To your specific question, the primal bound and also the cutoff bound are
set by SCIP automatically, when finding a new incumbent. The cutoff bound
itself will also be propagated.
(As a note propagation might be aborted due to some limit, meaning that it
might be possible to deduce even better bounds on variables. Also more
expensive algorithm could also lead to better bounds.)

> The second thing is about the estimate value for a node. I printed out
> the node selector rule used by scip, and I got "best estimate", so I
> think it is using this value to choose nodes in the tree, right? In the
> constraint handler when I create the two nodes I can give to each of
> them an estimate value, within the fourth parameter of the function
> SCIPcreateChild. I would like to modify this value for each node after
> solving it with the pricing, to have a more accurate value. Is there a
> way to do this, as a function "set node estimate" or similar? I was not
> able to find it in the documentation.
>

For now, there is no way of changing the estimate value after creating a
node.

> Finally, the third parameter of SCIPcreateChild is a "node selection
> priority of the node", for now I have set it to 1.0 for both nodes I
> create in the branching, but I was wondering which is the role of this
> parameter in the branching?
>

The priority is the first decision value on which a new node is selected.
As a strongly simplified answer children are chosen before siblings before
leaves by priority if the estimate is small enough. For more insight you
can also look into the nodesel_estimate.c file.

Best, Michael

> Thanks a lot for any help,
>
> best,
>
> Alessia
>
>
> --
> Alessia Violin
> Service Graphes et Optimisation Mathématique (G.O.M.)
> Université Libre de Bruxelles
> C.P. 210/01
> Boulevard du Triomphe
> B-1050 BRUXELLES
> Tel: 02 650 58 80 - Fax: 02 650 59 70
> Email: aviolin at ulb.ac.be
> Webpage: http://homepages.ulb.ac.be/~aviolin/
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>