[gecode-users] Schedule Branching Recommendations

[Graham, Justin G]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20070404/f8527e5d/attachment.htm>