[Scip] branching on constraints

[Gerald Gamrath]

Hi Alessia,

you are right: You need to set needscons to FALSE, because you do not
create constraints of your constraint handler, but the handler itself
needs to check solution candidates.

The integrality constraint handler is just the constraint handler that
ensures that integral and binary variables get integral values.
Actually, your constraint handler is pretty similar, it just checks the
integrality of the original variables.

Best,
Gerald

On 11.04.2013 11:36, Alessia Violin wrote:
> Hello Gerald,
>
> thanks for your suggestions. I will have a look at GCG, I didn't know
> about it! But as my pricing (with stabilization) is already working in
> SCIP, I will try to continue on this.
>
> I added a constraint handler class, define a new object in the main
> and include it in my scip, do I need to do more to activate it? For
> the moment the functions of my class are empty, but I tried to put
> some cout to see if it enters in the functions and in particular in
> the enfolp, and nothing appears. As parameters for the constraint
> handler I set
> sepapriority -100000
> enfopriority 100000
> checkpriority -100000
> sepafreq -1
> propfreq -1
> eagerfreq 1
> maxprerounds 0
> delaysepa FALSE
> delayprop FALSE
> delaypresol FALSE
> needscons TRUE
> (maybe the problem is here)
>
> What do you mean by integrality constraint handler? do I need to set
> somewhere that constraints are integer?
> I am a bit confused...
>
> Thanks again,
>
> Alessia
>
>
>
> On 04/10/2013 02:46 PM, Gerald Gamrath wrote:
>> 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
>