[Scip] Branch on original variables
Ambros Gleixner
gleixner at zib.de
Sat Apr 4 18:46:03 CEST 2015
Dear Bahareh,
Am 01.04.2015 um 22:58 schrieb Bahareh Eghtesadi:
> Also I have two more questions. I would appreciate your suggestions.
> First, is it possible to solve the master problem with interior point
> method using Soplex?
No, SoPlex only implements the simplex method.
> Second, I am giving an initial feasible solution to the master problem
> when creating it, and the corresponding dual variables are zero (Those
> duals that are obj coefficient in the subproblems). These cause my
> subproblems to add zero columns to the master problem. do you think
> there is a way to fix this?or I just have to change the initial solution?
I am not sure I understand your question. But maybe the
branch-and-price experts can answer this.
Kind regards,
Ambros
>
> Thanks
>
> On Wed, Apr 1, 2015 at 10:32 AM, Bahareh Eghtesadi
> <b.eghtesadi at gmail.com <mailto:b.eghtesadi at gmail.com>> wrote:
>
> Hi,
> I am now confused about how the callback methods CONSACTIVE and
> DEACTIVE are supposed to work. When I create two nodes with 0 as
> their node selection priority, it first goes into the left_node's
> consactive method, then prop and then goes into the pricing(in my
> case leftnode means where the upper bound of a variable is changed).
> I guess this is how it should work.
> But when I set the node selection priority of the right_node to sth
> larger, it first visits the right node, after implementing
> consactive and prop, it goes into DEactive method, and after that
> implements active and prop of the left_node! Then goes ahead with
> the pricing! Does this mean that there is sth wrong with my
> implementation?
>
> Thanks in advance.
>
> On Mon, Mar 30, 2015 at 2:07 PM, Bahareh Eghtesadi
> <b.eghtesadi at gmail.com <mailto:b.eghtesadi at gmail.com>> wrote:
>
> Hello again,
>
> That problem is solved. Actually I was following the Binpacking
> example, so I had also added SCIPreleasecons() in the branching
> rule after calling SCIPaddconsnode(). But when I remove that,
> SCIPconshdlrGetConss(conshdlr) returns the constraints. I am
> wondering how come it works in the example?
> However, after I get the conss in the pricing, I loop over all
> of them to see which one is active (using SCIPconsIsActive) to
> apply the branching decisions,but non of them is active. I have
> checked in the conshdlr, after going into the CONSACTIVE , it
> also goes into the CONSDEACTIVE method, and then returns to the
> pricing. I suspect this may be the reason that the constraint is
> not active? or this is how it should be performed?
>
> Thanks.
>
> On Mon, Mar 30, 2015 at 2:51 AM, Gerald Gamrath <gamrath at zib.de
> <mailto:gamrath at zib.de>> wrote:
>
> Dear Bahareh,
>
> do you also add the constraint via SCIPaddCons() or (better
> in your case) SCIPaddConsNode()?
>
> Best,
> Gerald
>
>
> Am 30.03.2015 um 07:48 schrieb Bahareh Eghtesadi:
>> Hi Gerald,
>>
>> Thanks for your explanation. I now understand how these
>> constraints work. So they are not basically added to the
>> subproblems causing additional constraints(which I was
>> trying to avoid).
>> So I am now creating two child nodes using
>> SCIPcreatechild, then create the constraint of the
>> conshdlr and add them to the node by SCIPaddconsnode.
>> After one iteration, when one constraint is added to a
>> node,and the prop is done , it goes in the pricing(to see
>> if any cons is active and if so change bounds), but
>> SCIPconshdlrGetConss(conshdlr) returns no constraint! I
>> have checked the conshdlr is found by SCIPfindConshdlr,
>> and it is the one attached to the node. Is there a way to
>> check if the constraint is being created? because the
>> SCIPcreatecon seems to be working fine, and I have no
>> other idea why it can happen.
>> I would appreciate your suggestions.
>>
>> Thanks.
>>
>> On Thu, Mar 19, 2015 at 8:00 AM, Gerald Gamrath
>> <gamrath at zib.de <mailto:gamrath at zib.de>> wrote:
>>
>> Dear Bahareh,
>>
>> you say that you store corresponding bounds and other
>> information in the consdata and use the CONSACTIVE
>> method to apply them in the pricer data. Both of this
>> uses a (set of) constraints, not just the constraint
>> handler. Of course, within the constraint handler, you
>> define how the data of a single constraint should look
>> like and what should be done if the constraint is
>> activated. So I don't really get your question, you
>> are already using constraints...
>>
>> I don't see how you could have the information about
>> bound changes for each node other than by storing them
>> in constraints sticked to nodes. You might store all
>> this in the constraint handler data, but you would
>> then need to keep track of all created nodes and store
>> a "copy" of the tree there, which is not convenient.
>> Also the CONSACTIVE callback is not called if no
>> constraint is activated...
>>
>> So I think there is no easy way to do this without
>> creating constraints.
>>
>> Best,
>> Gerald
>>
>>
>> Am 18.03.2015 um 19:02 schrieb Bahareh Eghtesadi:
>>> Hi Stephen,
>>>
>>> Thank you for your response.
>>> Actually I have been looking at the Bin Packing
>>> example. Here is what I have done so far: In my
>>> branching rule, I choose which pricing variable to
>>> branch on, create two nodes and store the
>>> corresponding bounds and other information in the
>>> consdata for each node. In the conshdlr, in
>>> CONSACTIVE method, I change the bounds stored in the
>>> pricer data.
>>> Do I still have to create the constraint of
>>> constraint handler in each node? Because I do not
>>> have any constraint in fact, I am using the handlr to
>>> apply changes to my pricer data(bounds). I set the
>>> NEEDSCONS flag to False, and was hoping that it would
>>> be enough.
>>> Also, in this case I would not need to check whether
>>> the "cons" is active in my variable pricer. Is this
>>> right?
>>> I appreciate your help. This is my first experience
>>> with SCIP, and I am afraid I have oversimplified
>>> everything.
>>>
>>>
>>> Thanks.
>>>
>>> On Wed, Mar 18, 2015 at 8:42 AM, Stephen J Maher
>>> <maher at zib.de <mailto:maher at zib.de>> wrote:
>>>
>>> Hi Bahareh,
>>>
>>> Branching on original variables can be performed
>>> similar to the way used for branching on
>>> constraints, i.e. Ryan-Foster branching.
>>>
>>> In order to implement this type of branching you
>>> will need to write your own constraint handler,
>>> branching rule and modify the variable pricer.
>>> The constraint handler will take some reference
>>> to the original variable and selected bounds as
>>> input and determine which master problem
>>> variables satisfy this constraint based on given
>>> variable bounds. In your branching rule, you will
>>> decide what original variable to branch on,
>>> create two branching nodes and then add a
>>> constraint of your constraint handler to each
>>> with appropriate bounds. In your variable pricer,
>>> it is then necessary to check whether any
>>> constraints of this type exist at the current
>>> node and apply the appropriate variable bounds on
>>> the original variables.
>>>
>>> An example of Ryan-Foster branching is given in
>>> the Bin Packing example included with SCIP. It
>>> should be possible to use this as a guide for
>>> your own rule branching on original variables.
>>>
>>> Cheers,
>>>
>>> Stephen
>>>
>>>
>>> On 13/03/15 07:14, Bahareh Eghtesadi wrote:
>>>
>>> Hi all,
>>>
>>> I am tying to implement a branch and price
>>> algorithm. I want to branch
>>> on the original variables that are not
>>> present in the master problem,
>>> and then change their bound in the pricing
>>> problems. But I am not sure
>>> how to do this. I think I can't use
>>> SCIPbranchvar directly from
>>> mybranchrule. If I use a constraint handler,
>>> I wouldn't make a
>>> constraint of that type (because there is no
>>> such constraint), then how
>>> can I include it in my branchrule?
>>>
>>>
>>> Thanks in advance.
>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de <mailto:Scip at zib.de>
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de <mailto:Scip at zib.de>
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>>
>>>
>>>
>>> --
>>> Regards
>>> Bahareh Eghtesadi
>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de <mailto:Scip at zib.de>
>>> http://listserv.zib.de/mailman/listinfo/scip
>>
>>
>>
>>
>> --
>> Regards
>> Bahareh Eghtesadi
>
>
>
>
> --
> Regards
> Bahareh Eghtesadi
>
>
>
>
> --
> Regards
> Bahareh Eghtesadi
>
>
>
>
> --
> Regards
> Bahareh Eghtesadi
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
--
______________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - TU Berlin - Berlin Mathematical School
http://www.zib.de/gleixner
More information about the Scip
mailing list