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:[EMAIL PROTECTED] Sent: Tuesday, April 10, 2007 8:26 AM To: Graham, Justin G; [EMAIL PROTECTED] 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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Graham, Justin G Sent: Wednesday, April 04, 2007 11:37 PM To: [EMAIL PROTECTED] 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 _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
