[Scip] branching on constraints

Wed Apr 17 18:51:58 MEST 2013

Hi Alessia,

it might be that some other constraint handler or branching rule already
performed branching. In order to be first, your constraint handler
should have a high CONSHDLR_ENFOPRIORITY.

You can check the statistics for the number of children created by the
plugins. In the interactive shell, you need to type "display
statistics", in the API, you call SCIPprintStatistics() after solving.
It also might be that the small instance is solved at the root node,
e.g., because a good solution is found.

The branching has nothing to do with the propagation, for which you
changed the timing mask. Branching is never done during the node
solving, but just at the end, after column generation is finished.
Propagation is a sort of node preprocessing, which tries to tighten the
local bounds of variables.

For storing your branching decisions, I would suggest you create dummy
constraints of your constraint handler which store your branching
restrictions. Furthermore, in the CONSACTIVE and CONSDEACTIVE callback,
they can update your pricing problem, and they can fix variables to 0
locally which do not comply with your branching decision. Please have a
look at the Binpacking and the Coloring example, which come with SCIP
(see the examples directory).

Best,
Gerald and Michael

On 17.04.2013 16:30, Alessia Violin wrote:
> Hello,
>
> thanks for the explanation.
>
> I changed needscons to FALSE, but still for a small instance it is not
> entering into the enfolp call of the constraint handler, I don't
> understand why. This instance needs branching, as the lp solution is
> not integer. I set timinmask parameter to SCIP_PROPTIMING_AFTERLPNODE,
> as I first want to solve the node with column generation and then I
> check for integrality and eventually branch, is that correct?
>
> For bigger instances it is entering, but I didn't managed to make it
> working yet. As I need to change the pricing after adding branching
> constraint, I would check if a certain constraint has been added to
> the current node. For this I found those functions, but I don't
> understand very well the difference between them and which one I
> should use: SCIPconsIsActive, SCIPconsIsEnabled and SCIPconsIsAdded.
>
> Best,
>
> Alessia
>
>
>
> On 04/11/2013 06:02 PM, Gerald Gamrath wrote:
>> 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
>