[Scip] creating variables for branching

[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





-- 
James Cussens
Dept of Computer Science &
York Centre for Complex Systems Analysis
Room 326, The Hub, Deramore Lane            Tel    +44 (0)1904 325371
University of York                                        Fax  +44
(0)1904 500159
York YO10 5GE, UK                               http://www.cs.york.ac.uk/~jc
http://www.york.ac.uk/docs/disclaimer/email.htm