[Scip] branching on constraints

[Gerald Gamrath]

Hi Alessia,

when you have no integrality restrictions on your variables, but only on
the sum of your master variables, you should implement a constraint
handler instead of a branching rule. In the scip_enfolp function, you
need to check for the integrality of your (implicit) original variables
and perform branching, if necessary. The enfolp-function is where the
branching really happens, in particular, the integrality constraint
handler calls the branching rules within his ENFOLP callback. Thus, your
branching rule is not called because no violated integrality
restrictions are identified.

By the way: did you already have a look at GCG (see
http://www.or.rwth-aachen.de/gcg/), the generic branch-cut-and-price
solver in the SCIP optimization suite? You only need to read in the
original formulation (expressed in the x_a^k variables) and possibly a
structure defining file and GCG will perform a Dantzig-Wolfe
decomposition which will probably end up in the same master problem
solved by branch-and-price. Within GCG, also the branching on original
variables as constraints in the master is already implemented. The
pricing problem is solved as a MIP by default, but you might even add
your own pricing problem solver if you have a better algorithm.

Best,
Gerald

On 10.04.2013 12:58, Alessia Violin wrote:
> Dear Ambros,
>
> thanks for your suggestion.
>
> I created a new branchrule class (I am using c++), and in the main I 
> create a new object of this type and add it with the function 
> SCIPincludeObjBranchrule. Then I am looking at the different functions 
> that are in the class, but it's not very clear to me when it enters in 
> them during the solving. I saw that in the preprocessing it enters into 
> the scip_initsol. But what about the scip_execlp? It seems to me that it 
> never enters in it and I suppose it's here I have to add the methods 
> SCIPcreateChild and SCIPaddConsNode, right?
>
> Then I have another doubt: as in my problem there are no integer or 
> binary variables, but I want a sum of variables (multiplied by 
> parameters) to be binary, how is SCIP dealing with this? Where should I 
> check for this condition and tell to branch or not?
>
> Sorry for those quite basic questions, it's the first time I implement a 
> branching rule.
>
> Thanks,
>
> Alessia
>
>
>
> On 04/08/2013 11:50 PM, Ambros Gleixner wrote:
>> Dear Alessia,
>>
>> constraint-based branching is rather straightforward to implement in
>> SCIP.  You have to add a new branching rule that uses the methods
>> SCIPcreateChild() and SCIPaddConsNode() in its branching callbacks.
>>
>> A very good example for this is the Ryan/Foster branching rule that has
>> been implemented in the binpacking example:
>>
>> http://scip.zib.de/doc/examples/Binpacking/index.shtml
>>
>> http://scip.zib.de/doc/examples/Binpacking/branch__ryanfoster_8c_source.shtml
>>
>>
>> Hope that helps,
>>
>> Ambros
>>
>>
>>
>> Am 08.04.2013 15:47, schrieb Alessia Violin:
>>> Hello,
>>>
>>> solving my problem with branch&price I would like to change the
>>> branching. Now I am branching on binary variables x_a^k = sum_j l_a^j *
>>> x_a^k,j <= 1, simply defining them as binary in the variable definition
>>> as they do not occur in the pricing. The variables for the pricing are
>>> l_a^j, and x_a^k,j are parameters that I calculate during the pricing.
>>>
>>> As those x_a^k variables are added only for the branching, I would like
>>> to eliminate them and branch directly on constraints sum_a l_a^j *
>>> x_a^k,j <=1 (they can be 0 or 1).
>>>
>>> Does it exist already in SCIP a branching rule on constraints? If not,
>>> shall I do it defining a new branching rule or is there an easier way to
>>> do it?
>>>
>>> Thank you in advance for any help and suggestion,
>>>
>>> Alessia
>>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip