[Scip] Branching on continuous variables in the quadratic constraint

[Wen-Yang Ku]

Hi Timo,

Thanks a lot for your explanation! I asked this because I noticed a  
great improvement after changing the the branching priority for the  
continuous variables for my problem. And the results so far are always  
correct.

Quoting Timo Berthold <berthold at zib.de>:

> Hi Wen-Yang,
>
>> Is there a general guideline on the
>> advantage (other than finding feasible solutions) using IPOPT?
>
> There are three points in SCIP where Ipopt is used:
> - to determine whether quadratic constraints are convex by checking the
> signs of their eigenvalues
> - for the local search heuristic subNLP
> - for the NLP diving heuristic
>
> If none of this is beneficial for you, there is no further added value.

I guess these techniques happen not to be influential on my problem :)  
That said, if I don't compile with IPOPT, SCIP won't have info on the  
convexity, so it's going to assume that the problem is non-convex.  
Then the spatial branching on the non-convex continuous variable will  
be used? If this is true, changing the branching priority on the  
continuous variable seems to make sense.

>
>> My question is that, is it still
>> algorithmic correct if I set the branching priority of these
>> continuous variables (W_j) higher, in order to make SCIP branch on
>> them before branching on the integer variables?
>
> I think that this will not have the intended effect; as long as SCIP has a
> fractional LP solution, it will keep branching on it.
>
> For SCIP nerds ;-): In SCIPbranchExecLP, branch.c, it is checked whether
> there are pseudo candidates of a higher priority than the highest LP
> candidate; however, there is no such check for the external candidates. It
> is debatable whether this is a bug or a feature. So or so, it seems to
> hinder what Wen-Yang tries to implement.
>
> @Wen-Yang, without any warranty (It did not check it myself):
> Adding
>    if( branchcand->externmaxpriority > branchcand->lpmaxpriority )
>    {
>       SCIP_CALL( SCIPbranchExecExtern(blkmem, set, stat, prob, tree, lp,
> branchcand, eventqueue, cutoffbound, allowaddcons, result) );
>       if( *result != SCIP_DIDNOTRUN )
>          return SCIP_OKAY;
>    }
> after the corresponding code block for pseudocands in  SCIPbranchExecLP()
> might give what you are asking for.

I will try this and see what happens. Thanks again!

Best,
Wen-Yang


>
> Best regards,
> Timo