[gecode-users] Schedule Branching Recommendations

[Graham, Justin G]

Thanks, that information was very helpful.

As for your question, I am not implementing the edge finding in the most
efficient manner since this is my first shot at the algorithm and I just
wanted to get something working quickly.  This is the basic idea of what
I plan to do now:

Status:  
Order the resources according to slack then order the tasks on the
selected resource.  This includes trimming the list to eliminate the
tasks that can go first, which is similar to the algorithm in Mozart.

Description:
Copy the accounting data structure to the description instance.

Note that multiple calls to status and description will give the same
result until a commit is called since I am just sorting the data.

Commit:
As an example, on the first alternative I will propagate with something
like this in a loop for all of the unordered tasks:
rel(home, s->end[firstTaskIndex], IRT_LQ, s->start[unorderedTaskIndex]);

After that I will mark the task as sorted in my data structure.

>From my experience, it seems as though I will need to copy my accounting
data structure to the description instance.  Then I will need to copy
the data structure from the description to the branching instance within
commit.  Originally, I was trying to avoid the extra copying but that
seems like the right way to pass the information to the next branching
instance.  Is that correct?

Also, I have another question:
Within the branching constructor there is a variable that denotes if the
data should be shared.  Do I need to pay attention to this variable
since I am carrying around extra data for the edge finding?  Or can I
just copy the entire data structure when the copy constructor is called?

Thanks,
Justin


-----Original Message-----
From: Christian Schulte [mailto:cschulte at kth.se] 
Sent: Tuesday, April 10, 2007 8:26 AM
To: Graham, Justin G; users at gecode.org
Subject: RE: [gecode-users] Schedule Branching Recommendations

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