[gecode-users] Schedule Branching Recommendations

[Christian Schulte]

Hi Justin,

a rather elaborate question that took me some time... Your findings about
status and description are accurate: you cannot change the space and you
should not change the branching in a way such that it becomes observable.
Remember, const does not mean that you do not change but that a second call
will deliver the same result (think of the mutable modifier, for example as
is used for ViewValBranchings).

The findings about commit are not correct: you are absolutely free to modify
your branching! Nothing suggests otherwise. And you are right to keep it
inside the branching, anything else would be very bad and difficult (you
would have to have spaces that are special in order to use them with your
branching, so not that hot).

Please do not hesitate to ask more questions of that sort! Do you consider
to only do branching or also propagation? Because there is a very
interesting issue for edge-finding/first-last: both propagation and
branching should share the same data structures to maintain their
information for efficiency. Support for sharing state among several
propagators/branching is on our todo list for a long time but we decided to
only do it when we implement exactly what you are now appareantly trying to
do...

All the best
Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 
-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Graham, Justin G
Sent: Wednesday, April 04, 2007 11:37 PM
To: users at gecode.org
Subject: [gecode-users] Schedule Branching Recommendations


I am attempting to implement an edge-finding algorithm that is similar to
that of firstsDist used in Mozart.  In order to do this, two major events
should occur for every branch:
 
- Propagation:  Generate propagators that specify that a given task will be
first.
- Accounting:   Keep track of what tasks have been ordered in some kind of
data structure.
 
I am assuming that a left branch specifies that a given task should be first
while a right branch specifies that the same task is not first.  In the case
that a task is not first, the appropriate data structure will need to be
updated so that the task should not be chosen until another task goes first.
It appears that streams are used to accomplish this type of accounting in
Mozart.
 
>From what I understand of the Gecode branching framework this is what I can
work with:
 
-status
Find if there are any tasks that need to be ordered.  At this point the
Space instance cannot be modified, but the Branching instance can be
modified in order to keep track of the tasks.
 
-description
Return some sort of identifier specifying which task should be ordered
first. The Space instance is still not modifiable here.
 
-commit
Perform the necessary propagation depending on the branching alternative
(left or right).  The Space is modifiable, but it appears that the Branching
instance should not be modified.  Is this a correct assumption?  Depending
on the branching alternative, I need to specify that the chosen task is
first or specify that the chosen task cannot be first using a data structure
for accounting purposes.
 
 
Given that information, is it OK to keep the additional data structures,
such as vectors, within the Space instance so that the ordered tasks can be
tracked?  I considered keeping this information in the Branching instance;
however this is not possible since I need to update the accounting data
within commit.  This needs to be done within commit since that is the only
place I know whether I am taking a left or right branch and I cannot edit
the branching instance according to my assumption listed above.  So, my
questions boil down to the following:
 
Is it bad to edit Branching member variables in commit?
Is it OK to edit native data structures contained in the Space instance
within commit?
Do you have any other recommendations for how I can keep track of the
ordered/unordered tasks?
 
Thanks,
Justin