[Scip] branching on constraints

Alessia Violin aviolin at ulb.ac.be
Fri Apr 19 11:01:38 MEST 2013


Hello Gerald,

thinking that it would have been easier to update the branching 
constraints with the new columns founded during the pricing, I created 
the whole set of possible branching constraint in the main, as a vector 
of linear constraints for the branch 0 and another for the branch 1, but 
without adding them to the model (no call of SCIPaddCons). Then in the 
pricing I am able to add new columns to them every time I found one. In 
the enfolp call of the constraint handler therefore I check if my 
solution is integral and if not I add the corresponding constraint to 
the node with SCIPaddConsNode(). The branching constraint is therefore 
not created in the constraint handler, but picked up from the vector of 
linear constraints I created at the beginning. This is what I was 
refering as "dummy constraints", but maybe I cannot use this strategy?
Printing the model after the branching I see the constraint I just 
added, but as I said then dual variables are zero so the pricing is 
already optimal and it's not finding new variables to add.

best,

Alessia





On 04/18/2013 05:59 PM, Gerald Gamrath wrote:
> Hi Alessia,
>
>> 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.
> These dummy constraint are from your own constraint handler? You create
> one at each node storing the branching decisions and add to the node
> using SCIPaddConsNode()? What do you update during pricing?
>
>> So in enfolp I create my branches and new nodes are added, along with
>> the branching constraints (printing the model I can see them).
> These branching constraints are again the dummy constraints or some
> linear constraints?
>
>> 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.
> If the branching constraints are you own constraints, they are not part
> of the LP and therefore have no dual solution. If they are linear
> constraints, they were perhaps not added to the LP. Did you set the
> initial flag to TRUE when creating them?
>
>> 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?
> If you add a constraint to a node, the consactive callback is called
> whenever the node is entered. You can use this callback to update your
> pricing problems, and possibly check whether new variables were added
> after you left the node the last time, whoch means that you have to
> check and possbily fix these variabes. However, you should not fix
> variables within the CONSACTIVE callback, but do that in the CONSPROP
> callback. You can do the fixing with SCIPfixVar() than and it will only
> be applied locally at the current node.
> The samediff Constraint handler in the Binpacking example should give
> you a hint about how you can do that.
>
> Best,
> Gerald
>
>> 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