[gecode-users] Idea for extending ViewBrancher

[Christian Schulte]

Hi Felix,

I have been thinking about your idea and I very much like it. 

How about the following generalization: one can pass to a brancher a filter
function (that is, a member function of the space). If a filter function is
passed it is used for selecting variables for branching: only if the filter
function returns true for a variable, the variable is considered for normal
selection. The function can be passed through the normal options for
branching (VarBranch) that is also used for tie breaking and randomized
selection. 

Would that make sense? It is less general than what Guido proposed but
easily available to the average modeler. I thought about it a little and I
know how to efficiently implement it.

Cheers
Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Felix Brandt
Sent: Saturday, August 28, 2010 9:52 AM
To: users at gecode.org
Subject: [gecode-users] Idea for extending ViewBrancher

Hi,

for a recent project I wrote a custom brancher (similar to the
ViewBrancher) that only branches variables within a certain interval.
The variables, which do not intersect the interval, are considered as if
they are already assigned.

In my case I wasn't interested in the values if they did not match the
given interval, but also did not want to add auxiliary variables and
constraints to be able to use standard branchers. Furthermore, I could
not just assign border values without breaking constraints. I assume
that such a brancher can also be advantageous in other setups, where one
wants to apply varying branching strategies to different parts of the
variable domains.

If this idea is of interest for the project, I could try to extend the
current ViewValueBrancher. Right now, I'm not sure where to start.
Probably adapting ViewBrancher<ViewSel>::status(const Space&) is a good
starting point, but it's quite deep in the object hierarchy so I assume
it's not *that* easy. Additionally, inheriting from ViewBrancher seems
to produce a lot of duplicated code (for brancher assembly and strategy
selection). Any suggestions?

Regards,
Felix

PS: If I miss something obvious or this feature is already present, I
would appreciate any hint :-)


_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users