Subject: Re: IJCAI-91 paper

From: Peter Cheeseman <[email-masked]>
Date: Thu, 28 May 1998 16:42:15 -0700 (PDT)

Hi Saleh,

  There has been a lot of research on phase transitions and hard
problems since the IJCAI paper, however, not much of it is relevent to
the time-table problem.  The main observations for scheduling problems
is that they are hierarchical in nature--i.e. the most constained
subproblems tend to be solved first, and this sets up a context for
the next most constrained subproblem(s) and so on.  Another
obeservation is that scheduling/timetable problems are self
critical--i.e. they tend naturally to the phase transition region.
This occurs because if there are free resources, they tend to get used
(scheduled) and this continues until there is barely enough resources
(e.g. rooms, money etc.) to go around.  At this point the demand for
the resources backs off, leaving the schduling problem at the phase
transition region.  Hope these obsevations help...

Peter Cheeseman
===============

-----------------------------------------------------------
   Date: Tue, 26 May 1998 19:32:55 -0400 (EDT)
   From: Saleh Elmohamed <[email-masked]>
   cc: Saleh Elmohamed <[email-masked]>
   MIME-Version: 1.0
   Content-Type: TEXT/PLAIN; charset=US-ASCII
   Content-Length: 891

   Hi Peter,

   In that useful and quite interesting paper of yours, 
   "Where the Really Hard Problems Are," IJCAI-91, 
   http://ic-www.arc.nasa.gov/ic/projects/bayes-group/NP/
   a number of questions and conjuctures were stated. Some
   of these questions can be derived from just reading it.
   I would be quite interested in any follow ups you or Bob 
   Kanefsky or Will Taylor may have done on the subject since 
   the publication of the aformentioned paper.

   A colleague and I have been looking at a number of scheduling
   cases, particularly timetabling. As the various sub-parts get
   resolved and depending on the type of constraints invloved, phase
   shifts or transitions occur from time to time throughout. 
   We believe that these transitions are of direct relation to the 
   constraints used in the problem.

   Any kind of analysis would be quite interesting.

   Would appreciate any pointers.

   Best,
   Saleh

---

From: Saleh Elmohamed <[email-masked]>
Date: Thu, 28 May 1998 21:48:53 -0400 (EDT)

Hi Peter,

Many thanks for the observations:

> the time-table problem.

There are probably few studies looking at phase transitions for 
scheduling (particularly job-shop) but have not read about or come 
across any. I raised this question during a talk I gave at the INFORMS conf 
in Montreal about a month or so ago, and after that talk two researchers 
from CRT, Univ. Montreal mentioned those studies. Well, I have yet to see 
any write ups on this. If you come across any I'd appreciate dropping me a 
note.

> The main observations for scheduling problems
> the next most constrained subproblem(s) and so on.

On this observation we found that to hope for getting a good solution 
we had to approach the problem from the hard-constrained side and then
worked our way downward. The difficult part was maintaining the 
"satisfiability" of the previous sub-parts' constraints as we moved into 
another sub-part, etc. It was sometimes necessary to relax some of those
medium constraints (those falling in the grayish region between hard 
and soft) and also further relax the soft ones (those that don't carry 
compulsory tags for total satisfication) if it was found that too many 
violations of the hard ones keep occuring during the solutions of the later 
subproblems. 

> Another

Yes. This is quite true and we observed it occuring as soon as we tried 
dealing with the soft constraints and at a number of times with even the 
medium constraints. Furthermore, we observed that if those resources were 
not sufficient (for example as the ratio between rooms and classes gets 
smaller and smaller) the phase transition region would tend to occur earlier 
and earlier in the hierarchical structure.

I really thank you for your observations and would appreciate anything you 
or Bob or Will might like to add.

Best regards,
Saleh