[Scip] Question about branching on master variables in SCIP

[Yongjia Song]

Hi Felipe,

Thanks a lot! That is also the only explanation that I could imagine. Just
wonder if SCIP does something unexpected.

Best,

On Fri, Aug 7, 2015 at 10:51 AM, Felipe Serrano <fserranom5 at gmail.com>
wrote:

> Hi Yongjia
>
> I can imagine that SCIP doesn't deal with the extra complications
> automatically.
> Actually, in the binpacking example explicit logicor constraints are added
> to the pricing problem in order to avoid generating the same packing.
> So I am guessing that you would need to add some constraint that avoids
> the generation of a fixed route to your pricing problem.
>
> I do not have any explanation for the behavior you describe apart from:
> SCIP might be generating the same variable on the branch where it is
> supposed to be fix to 0.
>
> Best,
> Felipe
>
> On Fri, Aug 7, 2015 at 4:02 PM, Yongjia Song <ysong3 at vcu.edu> wrote:
>
>> Hi Benny,
>>
>> Thanks a lot! I actually tried a set partitioning formulation with only
>> master variables, and claim them to be integer so branching has to be done
>> for these variables. I only specify a pricer as the one in the VRP example.
>> Will Scip automatically take care of the extra complication in pricing
>> because of branching? I actually tried this, and sometimes it gave the
>> correct solution(maybe out of luck) but it also happened that no progress
>> is made at all after the root. Any explanation on this? Thanks a lot!
>>
>> Best,
>> ------------------------------
>> From: Benjamin Müller <benjamin.mueller at zib.de>
>> Sent: ‎8/‎7/‎2015 3:50 AM
>> To: Yongjia Song <ysong3 at vcu.edu>; SCIP mailing list <scip at zib.de>
>> Subject: Re: [Scip]  Question about branching on master variables in SCIP
>>
>> Hi Yongjia,
>>
>> you are completely right, branching on the reformulated variables does
>> change the nature of your pricing problem. If your model does only contain
>> the routing variables and you declare them as integral then SCIP will
>> branch on those as SCIP would usually do. The user has to respect the
>> branching decisions made by SCIP in his pricer. You could add your own
>> branching rule in order to branch on the original variables even though
>> they are not in the model (see Ryan/Foster branching in the Binpacking
>> example).
>>
>> Note that, in the VRP example the routine variables are continuous and
>> thus branching will only be applied on edge variables. Those branching
>> decisions does not influence the pricing problem too much (excluding edges
>> from the graph).
>>
>>
>> Best,
>>
>> Benny
>>
>>
>> On 08/06/2015 08:01 PM, Yongjia Song wrote:
>>
>> Hi all,
>>
>> I have a question about how SCIP handles branching when only the master
>> variables present in the model. Taking VRP as an example, suppose we only
>> have the route variables (without the original edge variables or the
>> linking constraints between edge variables and route variables), and we
>> impose the integrality constraints on these variables, it is not clear how
>> branching on these variables are implemented in SCIP. Indeed, when a
>> branching decision is made on some route variable, it complicates the
>> pricing by forcing the pricing algorithm to avoid generating that route.
>> Without specific problem structure, it is not clear to me how SCIP handles
>> this case. Thanks a lot for your help!
>>
>> Best,
>>
>> --
>> SONG, Yongjia
>> Assistant Professor
>> Department of Statistical Sciences and Operations Research
>> Virginia Commonwealth University
>> PO Box 843083
>> Richmond, VA 23284-3083
>> 804-828-1149
>> Ysong3 at vcu.edu
>>
>>
>> _______________________________________________
>> Scip mailing listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>>
>>
>> --
>> ______________________________
>> Benjamin Müller
>> Zuse Institute Berlin
>> Takustr. 7, 14195 Berlinbenjamin.mueller at zib.de+49 30 841 85-195
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>>
>


-- 
SONG, Yongjia
Assistant Professor
Department of Statistical Sciences and Operations Research
Virginia Commonwealth University
PO Box 843083
Richmond, VA 23284-3083
804-828-1149
Ysong3 at vcu.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150807/aed7376f/attachment.html>