[Scip] branching on constraints

Fri Apr 19 11:13:18 MEST 2013

Hi Alessia,

just one thought: it sounds like you could be adding one of your dummy 
constraints locally at multiple nodes of the tree.  This is not 
possible.  You have to create a new local constraint for each node.  (In 
the implementation, the constraint data structure has a pointer to the 
nodes where it was added in order to support its de/activation when 
moving through the tree.)  I don't know whether that has created any 
troubles for you so far.

Ambros

Am 19.04.2013 11:01, schrieb Alessia Violin:
> 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
>

-- 
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner