[Scip] branching on constraints

Gerald Gamrath gamrath at zib.de
Fri Apr 19 11:15:49 MEST 2013 

Hi Alessia,

do you set the initial flag of the linear constraints to TRUE?

Do I understand you correctly that for each original variable x, you
create one constraint with all master variables that have x = 0, and one
with all master variables with x = 1? If you branch x to 0, you say that
the first constraint has a right hand side of 1 and second constraint a
right hand side of 0? For branching x to 1 the other way around? In
priciple, this is a valid possibility, but it has two drawbacks:
1) This probably consumes a lot of memory, since the constraints with
master variables with x = 0 are very dense.
2) You cannot add the same constraint at different nodes in SCIP, but
you will branch on the same variable at different nodes, so creating
each constraint once in advance is not possible, you have to generate
them when needed.

I always prefer the variant with a dummy constraint which is not added
to the LP, but just does propagation. It just stores that x has been
branched to 1 and then iterates over all variables, fixing all master
variables to 0 which have x != 1. This is essentially the same as the
constraint, but you don't get so many additional constraints in your
master, just a lot of variables are fixed to 0 by branching. Please have
a look at the Binpacking example, the samediff constraint handler does this.

Best,
Gerald

On 19.04.2013 11:01, Alessia Violin wrote:
> 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
>

More information about the Scip mailing list