[Scip] branching on constraints

Alessia Violin aviolin at ulb.ac.be
Thu Apr 18 15:37:56 MEST 2013 

Hello,

sorry to bother again but I still have troubles...

For now I am trying to make it working on bigger instances, then I will 
go back on why it's not branching on the smaller ones.

As you suggested I have dummy constraints for branching, initialized fro 
the beginning but not included in the model, always updated during 
pricing and added to the model of a node when needed. So in enfolp I 
create my branches and new nodes are added, along with the branching 
constraints (printing the model I can see them). But then, in the new 
node, when it goes back to pricing it doesn't find any new column, as 
dual variables associated to the new constraint are null, and therefore 
it finds that the lp is already optimal. So the solution is always the 
same and it keeps on branching onto the same constraint in an infinite loop.
I tried to look for dual variables of the transformed constraint, as I 
am doing for all other constrains, but actually it is not finding the 
transformed constraint.

About the consactive, when is it accessing it? I tried but it's never 
going into this function. Indeed, I would like to locally fix some 
variables after the branching decision, should I do if with the method 
SCIPfixVar? but will it be valid only at the current node or globally?

I looked through the examples but I didn't understand how this is 
working, sorry.

Thanks again,

Alessia


On 04/17/2013 06:51 PM, Gerald Gamrath wrote:
> 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

-- 
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/

More information about the Scip mailing list