[Scip] branching on constraints

Thu Apr 18 17:59:19 MEST 2013

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
>