[Scip] creating variables for branching

[Ambros Gleixner]

Dear James,

I am sorry that you have not received an answer, at least not over the 
mailing list.  Unfortunately, the SCIP team has been very busy with 
organisational duties over the last weeks.

Short answer: Yes, this is a reasonable way to achieve what you want, 
certainly it is the quickest way implementation-wise and I guess the 
additional improvement you can gain by implementing your own branching 
rule is rather small.

This is because the auxiliary binary variables you add now are not only 
used for branching but in performance-relevant techniques like, probing, 
propagators, and conflict analysis.

Without auxiliary variables you would lose these and reimplementing them 
for your special case is tedious.

So I would say it only makes sense to look into more problem-specific 
implementation if you see that the LP solution time is a bottleneck.  Is 
that the case?

Also, is it really necessary to increase the branching priorities on 
these auxiliary variables, or would SCIP find out itself that branching 
on them is a good idea?

Best regards,
Ambros



Am 13.11.2014 um 18:21 schrieb James Cussens:
> Dear SCIP,
>
> I use SCIP to find "optimal" directed acyclic graphs (DAGs). All my
> variables are binary, each one specifying that a certain set (possibly
> empty) of vertices constitute the "parent set" of some other vertex.
> Call these "family variables". There may be very many possible parent
> sets for a given vertex . Since there can be only one parent set for a
> given vertex in any solution this gives rise to a set partitioning
> constraint for each DAG vertex.
>
> Recently I've been getting some encouraging results by doing the following:
> 1) Creating "redundant" variables (with zero objective) indicating
> directed edges and constraining these to be the sum of the relevant
> family variables.
> 2) Marking these edge variables as not to be aggregated
> 3) Increasing their branching priority so that they - not the family
> variables get branched on.
> 4) Use SCIP's default strategy for building the search tree
>
> So these variables are created purely to effect a certain branching
> strategy - it's a sort of SOS approach. The better performance is
> because we get a smaller, more balanced tree. (There's some other
> stuff you need to do to get it to work well which is irrelevant to my
> question.)
>
> My question is (finally!):
> Is this a reasonable way of doing this? My thinking is that by having
> these variables, SCIP can treat them like any other variable and
> compute pseudo-costs etc for each of them, which intuitively seems
> useful. It's also easier than writing a branching rule but perhaps
> that is just my laziness.
>
> On the other hand I'm "clogging up" my binary IP with extra variables
> which SCIP would normally just delete.
>
> Any views/ideas?
>
> James
>
>
>
>
>

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