**************************************************************************
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 :-)).