CSCE990-05, Fall 1999: Theory and Practice of Constraint Satisfaction                                                            Main page of the course. 

 Contents: Course description: Constraint satisfaction has emerged as a successful approach to articulate and solve many industrial problems such as design, scheduling, and resource allocation.  This course reviews the foundations of constraint satisfaction and the basic mechanisms developed in this context (e.g., search, backtracking, and consistency-checking algorithms).  A special emphasis is made on new directions in the field, such as strategies for decomposition and for symmetry identification.

 The exact reference of each of the papers listed below can be found in the extensive, but subjective, bibliography. Papers can be found in the Library (UNL users: check also the electronic reserves) or retrieved from the instructor.

 Date
August 23rd  Introduction and overview of issues and techniques
Required reading: 
  • Tsang, Chapter 1: `Introduction'.
  • Meseguer (AICom 92): `Constraint Satisfaction: An Overview'
    		•
    Additional reading: 
  • Introduction by Barták 
  • Kumar (AIMag  92,): `Algorithms for Constraint Satisfaction Problems: A Survey.'
  • Dechter, R. (1998): `Constraint Satisfaction.' To be published in the MIT Encyclopedia of the Cognitive Sciences (MITECS), 1998.
  • Tsang, Chapter 2: `CSP Solving--An Overview'.
    		•
    August 25th Topic:  Main definitions & foundations. 
    Davis (AIJ 87): `Constraint Propagation with Interval Labels.'
    Additional reading: 
  • Montanari (IS 74): `Networks of Constraint: Fundamental Properties and Applications to Picture Processing.'
  • Dechter: `Constraint Networks' AI Encyclopedia `92
  • Mackworth:  `Constraint Satisfaction' AI Encyclopedia `92.
    		•
    August 30th Topic: Consistency-checking algorithms. 
    Mackworth  (AIJ  77): Consistency in Networks of Relations
    Additional reading: 
  • Tsang, Chapter 3. `Fundamental Concepts in the CSP.' 
  • Tsang, Chapter 4. `Problem reduction.'
  • Bliek & Sam-Haroud,  (IJCAI 99 ), `Path Consistency on Triangulated Constraint Graph.'
    		•
    September 1st Topic: Consistency-checking algorithms. 
    Mackworth & Freuder (AIJ  85): `The complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems.'
    Additional reading: Same as previous session.
    September 6th  Labor Day
    September 8th Topic: Backtracking mechanisms. 
    Prosser (CI 93): `Hybrid Algorithms for the Constraint Satisfaction Problem.'
    Additional reading: 
  • Haralick and Elliott (AIJ 80): `Increasing Tree Search Efficiency for Constraint Satisfaction Problems.'
  • Nadel (CI 89): `Constraint Satisfaction Algorithms.'
    		•
    Starting this date, we are running one lecture behind the original schedule.
    September 13th Topic: Backtracking mechanisms. 
    Again, Prosser (CI 93): `Hybrid Algorithms for the Constraint Satisfaction Problem.'
    September  15th Topic: Backtracking mechanisms. 
    Kondrak & van Beek (IJCAI 95): `A Theoretical Evaluations of Selected Backtracking Algorithms.'
    September 20th Topic: Variable/value ordering. 
    Geelen (ECAI 92): `Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems.'
    Additional reading: 
    Tsang, Chapter 6. `Search orders in CSPs.'
    September 22th Topic: Variable/value ordering. 
    Bacchus & van Run (CP 95): `Dynamic Variable Ordering in CSPs.'
    Additional reading: same as previous week.
    September 27th Topic: Foundations. 
    Freuder (CommACM 78): `Synthesizing Constraint Expressions.'
    September 29th Topic: Constraint arity. 
    Bacchus & van Beek (AAAI 98): `On the Conversion between Non-Binary and Binary Constraint Satisfaction Problem.'
    October 4th Topic: Network properties. 
  • Freuder (JACM 82): `Sufficient Condition for Backtrack-Free Search.' 
  • Freuder (JACM 85): `A Sufficient Condition for Backtrack-Bounded Search.'
    		•
    Additional reading: 
    Dechter & Pearl (IJCAI 91): `Directed Constraint Networks: A Relational Framework for Causal Modeling.'
    October 6th Topic: Constraint types. 
    Liu (IJCAI 95): `Increasing Functional Constraints Need to Be Checked Only Once.'
    Additional reading: 
    Régin (AAAI 94): `A Filtering Algorithm for Constraints of Differences in CSPs.'
    October 11th Topic: Constraint types
    Régin (AAAI 94): `A Filtering Algorithm for Constraints of Differences in CSPs.'
    October 13th Dr. Revesz will be conducting the course as the instructor is out of town.
    Topic: CSP application in Databases
    Shu H. (ECAI 98): `Using Constraint Satisfaction for View Update Translation.' 
    Longer version: `Formulating View Update Translation as Constraint Satisfaction.'
    October 18th Fall Semester Break
    October 20th Topic: Constraint properties. 
    van Beek (AAAI 92): `On the Minimality and Decomposability of Constraint Networks.'
    October 25th Topic: Phase transition. 
    Cheeseman, Kanefsky, and Taylor (IJCAI 91): `Where the Really Hard Problems Are.' 
    See the authors' page about this paper.
    Additional reading: 
  • Hays (American Scientist 97) `Can't get No Satisfaction'  (less technical.)
  • Gent et al. (APES-TR 12-1999) `Constrainedness of Search.'
  • Gent et al. (APES-TR 08-1998) `Random Constraint Satisfaction: Flaws and Structure.' 
  • Gent et al. (APES-TR 97): `How not to do it.'
    		•
    October 27th Topic: Decomposition. 
    Freuder & Hubbe (95, CP 93): `A Disjunctive Decomposition Control Schema for Constraint Satisfaction.'
    November 1st Topic: Decomposition. 
    Dechter & Pearl (AIJ 89): `Tree Clustering for Constraint Networks.'
    Find details in Section 7.6, pages 212--234 in Tsang's book.
    November 3rd Topic: Decomposition. 
    Choueiry & Faltings (ECAI 94): `Decomposition Heuristic for  Resource Allocation.'
    Novermber 8th Topic: Decomposition. 
  • Freuder & Hubbe (IJCAI 95) `Extracting Constraint Satisfaction Subproblems'
  • Freuder (IJCAI`93): `Using Inferred Disjunctive Constraints to Decompose Constraint Satisfaction Problems.' 
    		•
    November 10th Topic: Decomposition. 
    Choueiry & Noubir (KSL-TR, FLAIRS 97): `A Disjunctive Decomposition Scheme for Discrete Constraint Satisfaction Problems Using Complete No-Good Sets.'
    Additional reading: 
    Jégou (AAAI 93): `Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems.'
    November 15th Topic: Interchangeability. 
    Freuder (AAAI 91): `Eliminating Interchangeable Values in Constraint Satisfaction Problems.'
    November 17th Topic: Interchangeability. 
  • Benson & Freuder (ECAI 92): `Interchangeability Preprocessing Can Improve Forward Checking Search.'
  • Haselböck (IJCAI 93): `Exploiting Interchangeabilities in Constraint Satisfaction Problems.'
    		•
    November 22nd Topic: Constraint Databases Tutorial by Dr. Revesz. 
    Constraint Databases, Chapt 11, Book: Constraint Programming. Authors: Mariott and Stuckey.
    November 24th
    Student Holiday
    November 29th Topic: Interchangeability. 
    Choueiry & Noubir (KSL-TR, AAAI 98): `On the Computation of Local Interchangeability in Discrete Constraint Satisfaction Problems.'
    December 1 Topic: Modeling & Reformulation. 
    Nadel (IEEE 90): `Representation Selection for Constraint Satisfaction:  A Case Study Using n-Queens.' 
    (If time allows: lecture on reformulation: `Issues, Metrics, and open Problems.')
    CANCELLED Topic: Modeling and Reformulation. 
  • Ellman (IJCAI 93): `Abstraction via Approximate Symmetry.'
  • Lecture on reformulation: `Issues, Metrics, and open Problems.'
    		•
    CANCELLED  Topic: Modeling & Reformulation: 
    Wallace & Freuder (CP 98) `Suggestion Strategies for Constraint-Based Matchmaker Agents'
    December  6 Topic: Extending CSPs-- Dynamic CSPs. 
    S. Mittal, B. Falkenhainer (AAAI 90): `Dynamic Constraint Satisfaction.'
    December  8 Topic: Extending CSPs-- Partial Satisfaction/Optimization. 
    Freuder (IJCAI 89): `Partial constraint satisfaction.'
    Additional reading: 
  • Tsang, Chapter 10. `Optimization in CSPs.'
  • Freuder & Wallace (AIJ 92): `Partial constraint satisfaction.'
    		•
    CANCELLED Topic: Local Search. 
    Minton et al. (AAAI 90): `Solving Large-Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repair Method.'
    Additional reading: 
  • Selman et al. (AAAI 92): `A New Method for Solving Hard Satisfiability Problems.'
  • Tsang, Chapter 8. `Stochastic Search Methods for CSPs.'
    		•
    December 15 Project/paper presentation if applicable. Wrap-up session and discussion of potential theses projects

    Additional topics:
    The students are encouraged to propose alternative topics, more related to the their own research interests. Here is a list of possible areas:

    Course support: Handouts: Related material from the Web:
    Courses: Groups: Archives:

    Return to the main page of the course. 


    Last modified: Wed Nov 16 11:25:26 CST 1999