************************************************************************** Note Taker: Minh Binh Do Date: Feb 23 Topic: Some CSP technique in solving Scheduling (encoding) problems. ************************************************************************* AGENDA OF TODAY CLASS: 1. CSP Model and PCP Scheduling: Page 41-71: + Contention Heuristics. Variable Ordering. + ARC-B Consistency. + Optimization Through repreated calls. 2. Iterative Approaches: Page 72-93, 35-39: + Taxonomy of conflict & repairs. + Mapping of conflict to repairs. Note: All the page numbers are regard to the "Knowledge-Based Scheduling" tutorial (Steve Chien & Stephen Smith). ************************************************************************* Today, I became Rao's first victim in the extra class-note department. The result is that other classmates will have to suffer my lousy notes for the third time in 5 weeks :-(. Rao starts the class with issues regarding the grading of the class. He suggests that we will have one take-home midterm, and some project or survey paper make up the final. Rao intends to give the midterm one week after the Spring-break, so he can make sure that everyone can have a nice vacation. The purpose of the take-home exam will be to make people read all the papers and tutorials that he gave out in the class (it's already around 500 pages until now). He will set up the exam so we can ask him anything, as long as we don't make him do it for us. For the final, he seems to be more interested in the projects than some survey papers. Rao said that even if we choose the survey paper option, we should still add something of our own, not neccessary the new stuffs, but at least should be able to explain something that is not clear before. If you choose to do the project, then it would be like "encoding SAT/CSP for planning with conditional effect", or something of that difficulty. Rao encourage students with good idea just come to his office and talk to him. He suggest one good idea, that he mentioned to his students many times before but noone actually did it, is to explain for him why Ginsberg's paper is an interesting one. One more small thing is that we will have a rest day in April 18, and Rao will hold a makeup class after that. CLASS BEGIN: Like I wrote above, we will concentrate on Steve Chien's tutorial in this class, and all page numbers are regarded to that tutorial. It's kind of bad that noone (include me) glanced at that paper before comming to class. So, please don't be surprise if my note is a little of low quality :-) +We will start with page 47. They talk about 3 different CSP techniques which are important for scheduling (remember 3 main techniques for general CSP that Rao talked in the last class? These two sets are overlap on 2, and has one different from each other). In the general CSP, we treat all different constraints, and constraint conflicts the same, but scheduling people tend to separate them into different "class", which lead to different types of conflict, and different specific techniques in repairing those conflicts (Remember that we only talk about iterative approach (local search), which try to repair a complete assignment here). + Now, Rao suddenly jump back to page 35-38. Rao said that the picture in page 38 is important, and it's great if you can understand it. Basically, page 35-38 talk about the repair strategies. Page 35 lists some of them. However, they guarantee nothing about the optimal, they just kind of just better than the random repair. They are some thumb rules on how to map failures to the rapairing techniques. + We move up 20 pages to pages 48-5?: They talk about the basic things about CSP and Job-Shop Scheduling. Nothing special because we already discussed them last week. There is a cute picture in page 52 about JSS with single-capacity problem. Note that we can only have this graph if we have the encoding as binary CSP (think about how can we represent the constraint involve more than 2 variables conveniently??). To have a graph representation, we have to compile away all disjuntive constraints, so we can assume that the CSP is a big conjuntive set of constraints between two variabes. One may ask a question about why we are so hyped about the Graph representation. Actually, the constraint-graph can be used effectively as the starting point for the constraint propagation by picking up any edge (represent one constraint) and do ARC-Consistent analysis, which is by far the most popular consistent-enforcement technique. Note that in general, we can only do ARC-Consistency upon a constraint if only less than or equal to 2 variable in that constraint are unassigned. If we have a binary-CSP problem, then we can do ARC-Consistency enforcement on any constraint without have to wait until some variable to be assigned a value. + Page 54: There is a small example about how ARC-Cons. cutting down some partial assignment, and limit the search. + Suddenly, Rao talk about something that I can't figure out the page related to this topic. He mention that if we don't have disjuntive precedence relation, then we can do topological short to find a consistent assignment. In scheduling, we normally only talk about qualitative constraint ( A before B), but not quantitative constraint. The simplest form of quantitative constraint may be: A should be from 6-8 time units before B. Having this type of constraint will lead to the General Temporal Constraint Network (GTCN) problem (page 61->..). If we don't have this type of constraint, then we will have the Simple Temporal Problem (STP). Return to the topic at the beginning of this paragraph, we assume that if we have a graph representation of the CSP problem, then we will have no consjuntion. It's true if we think about the whole set of constraint, but actually we will have some form of *hidden* disjuntion inside the constraint. One resource-compete constraint between A and B means that "A before B" or "B before A". Disjutive constraints normally make the problem much harder to solve (that's why most people try to avoid it by split them to a set of conjuntive constraint, and throw into the search space). Normally, we need to do k-size propagation for disjuntive, and it's too costly. In solving the problem, we need a nice mix between constraint propagation (derive new constraint, equal to theorem proving), and search. Both of them are costly if we do alone, but a little of this, and a little of the other will be the best choice. When talking about constraint propagation, what is the cheapest technique? Obviously, it's one-consistent enforcement. However, we normally don't have many 1-size constraints to do 1-consistent enf., so people generally use the other popular technique called "forward-checking". Unlike k-consistent enforcement, which require no variable to be assigned, forward-checking will check out inconsistent value from remaining variable in the constraint that has all but one of it variable commited to some value. Actually, when some CSP solver claims that they do ARC-Consistentcy, or Full-Consistentcy, they actually follow the approach similar to forward-checking, when they try to prune out inconsistent pair of values upon the current partial assignment, when the constraint only have 2 (or k) variables unassigned. Rao said in the class that for encoding with many conditional constraints of type A => B, then doing consistent-enforcement maybe too costly, but forward-checking will be the perfect fit. + In the next few pages, they talk about some more sophisticated techniques (other than those in page 43->..). I'm kind of lost in this part. + Then, Rao jump back to page 43 and so on (my head starts spinning after all those sudden moves back and forth). In page 43, they talk about the the demand profile. I remember I mentioned about them a little bit in my last note. Basically, if we have a task T that should start as soon as 0 time point and finish as late as time point 5. It has 3 time units duration, and that task use machine A. Then we can be sure that the probability that A is used at time point 2->3 is 100%, if we assume that the distribution of T's starting time is uniform between 0->2, then the probability that we use A at time point 1 and 4 is 50%, and 0% before 0, or after 5. Using this information, we can find out if some machine will be busiest at some timepoints, and we will try to concentrate on tasks that use that machine first, so if we fail, we will fail at the top of the search tree. Page 43->45 has the example on how to use the demand profiles information. + When Rao talk about the demand profile, he also go on and talk about the general var-ordering too. He said that every var-orderings follow the same fundamental of most-constrained variable first. However, the semantics of most-constrained will be different in different situation. In the general CSP, it could be the variable with less value left (most constrained in the value-domain), or variable appear in the biggest number of different constraints (most constrained with other variables). In the profile-demand, it's a task that most constrained with other competing tasks (for the same machine). + Now, we are near the end of the class (actually, we are 1.5 minutes pass the end), and Rao quickly go over some specific techniques in page 57->..: .page 57: ARC-B consistency technique (It's mentioned in the tutorial, and also in Beck's paper) .page 58: Edge-finding (similar to ARC-B, but not just between 2 tasks, but the checking is from one task to a set of task). .page 64: Similar to ARC-B, but in term of *Slack* values. Slack values are not only used to prune out inconsistent assignment, but also can be used as heuristic for variable ordering (I think that it's similar to DVO, with which the most-constrained means the most constrained on the domain of the starting-time variable). Rao said that the slack-based heuristic is mostly used in the time-point encoding, and the demand-profile is used more in the PCP. Actually, it's not very difficult to see why. END OF THE CLASS. My only hope is that next time Rao won't ask me if I did take several extra-note or not :-)).