Constraint Reasoning

CSE 5692
Florida Institute of Technology
Instructor: Debasis Mitra

Department: Computer Sciences

AAAI resorces on constraint-based reasoning


A constraint benchmark library


Spring 2008:

Class: Crawford 401, TR 8-9:15 pm.
Plan for the senester.
HomeWork 1
HomeWork 2
Course Feed Back due 4/10/08

Fall 2005:

Class Crawford S402, Friday 5-8 pm.
9/3/05: Johannes on Assignment 1 (25 min)
Benjamin on minimal network etc, and Assignment 2 (1 hr)
Gary on Arc Consistency from text and Mackworth's paper) (1 hr)

9/9/05: Johannes on Path Consistency from book plus Macwarth's paper (1 hr)
Benjamin on Higher level consistency, sectio 3.4-3.5 (1 hr)
Gary on Section 3.6 and 3.7 (30 min)
Homework 2 discussion: all

9/16/05: Benjamin (20 min max): i-consistency etc. of last class, sec 4.1,2
Johannes: directional consistencies (1 hr),
Gary: width and local consistency sec 4.3 (30 min)
Benjamin: Adaptive consistency bucket elimination sec 4.4 (30 min).
Homework 3 (ch 3): Due 9/23/05: Exc 1, 4, 7, 12, 17, find "csplib" on the web and formulate 2 problems therein, pick up any one of the Escher sketches and TRY to formulate it as a constraint satisfaction problem

9/25/05: Ch 5 Look-Ahead: Gary: 5.1 & 2 up to BackMarking
Benjamin: 5.3 Look-ahead strategies
Johannes: 5.3.3 cycle-cutset onwards through end
Homework 4 (Ch 5): Due 10/7/05: Exc 3 a, b, c, d; Exc 4 c d; and Exc 12 a, b.

9/30/05: Ch 6 Look-Back Strategies: Johannes: 6.1-2 two back-jumping algorithms (40 min)
Benjamin: 6.3-4 complexity and learning algorithms
Gary: 6.5-end: Look-back on SAT, integrated algorithms, and phase transition

10/7/05: Johannes: Protein docking as a constraint reasoning problem (30 min),
Gary: Temporal reasoning problem (ch 12 up to including 12.2.0 p348, 30 min),
Benjamin: 12.2.1 - end (30 min),
Re-doing Ch6: Gaschnig+Graph-based bj: Benjamin (25 min),
CBJ+FcCbj: Gary (25 min), Graph-based learning, SAT-cbj-learning: Johannes (25 min)

10/14/05: Benjamin: TCSP end parts (30 min)
HW3: 1,4 - Gary, 7,12 - Benjamin, 17 - Johannes
HW4: 3 - Gary, 4 - Johannes, 12 - Benjamin
(Time permiting) Conflict-directed Bacjumping: ??

10/21/05: Spatio-temporal calculi (from Renz slides): Mitra (30 min)
Explanation in CSP and proposal for TCSP: Benjamin (40 min)
Reasoning operators with Quantitative Cyclic-time calculus and Star-calculus (30 min)
2D Shape matching with Bigger algorithm: Johannes (30 min)

We will have to re-do the previous class and push the schedule by 1 day
10/28/05: Gary: Reasoning operators with Quantitative Cyclic-time calculus and Star-calculus (30 min)
Explanation in CSP and proposal for TCSP: Benjamin (40 min)
2D Shape matching with Bigger algorithm: Johannes (30 min)
Benjamin: Golomb ruler problem ch5-12

11/4/05: Tractability of CSP Ch 11.1&2: Gary [Backup: Johannes] (45 min)
Explanation in TCSP: Benjamin (30 min)

11/14/05 Monday 6--9 pm (instead of 11/11/05 holiday): Ch 11.3 -11.4.3: Johannes [Backup: Benjamin] (45 min)
Non-linear TCSP: Gary (1 hr)

11/18/05: Ch 11.4.4 -End: Benjamin (45 min) [Backup: Gary]
Demo of 2D shape matching and proposal for using Star-calculus: Johannes

12/2/05: The exercise on gadget: express => using (or, not): Benjamin (20 min)
On three projects introduced in the class (15 min: me)
Project presentations: Gary, Benjamin and Johannes (30 min each)

I need your project report or demo (Johannes) by Friday in order to grade it in time.

Fall 2004:

Programming Assignment (Due Oct 27): (1) Empirically check if AC enforcement and PC enforcement operations are commutative or not,
(2) If not, then does one of the two orderings (AC then PC, and PC then AC) produces tighter network than the other one, in general case?
(3) Modify the PC algorithm (by allowing i=k and j=k) so that it coverges to a network that is the stable network of AC and PC run alternatively until relaxed. Verify the modified PC is really satisfying the later objective.
Run on at least 10 examples before making any conclusion.

Self-study Presentation:
Find at least one paper on the theme you have chosen to work on and present it to the class. Abstract submission due Oct 20. Presentation schedule will be announced (1 hr each).

12/8/04: Ch 12: Mitra

12/15/04: Ch 11 presentation assignment
Venkatesh: Sec 11.1 and 2
Yang: Sec 11.3 through 11.4.4 inclusive
Gandhali: Sec 11.4.5 through end



Constraint reasoning is a way of looking at many computational problems. It involves a set of variables, their domains, and relational constraints between some of those variables regarding what values they can take. An example is the map coloring problem where the variables are the regions on a map, all variables/regions have the same domain as a finite set of available colors to choose from the regions, and the constraints are the adjacency information between the regions in the map and an assertion that no adjacent regions may have the same color. Given an instance of such a map-coloring problem there may or may not exist a solution. When the question is to check if there exists a solution or not - it is called a constraint-satisfaction problem (CSP). Alternatively the question could be to find a solution (e.g., a color assignment to each region) if there exists one. This type of view (variables, constraints) of problems is called constraint reasoning. Sometimes they could be optimization problems also, when the best solution is to be found, not just any solution. Scheduling problems are such constraint optimization problems. In the last few decades constraint reasoning area have been heavily researched within the AI. Apparently 20% of the papers in the major AI conferences come from related areas.

The Syllabus

Fall 2003:


Class Room: EC129, Time: Wednesday 6:30 pm - 9 pm
Project reports should be written using the Chicago-style, information about it is available at


Students without AI background need to Study at least the following materials:
Introduction (Ch 1), Problem solving by searching (Ch 2), Informed search methods (Ch 3), Game playing (Ch 5) from the standard AI Text book of Russell and Norvig, ISBN 0-13-103805-2, Printice-Hall, 1995,
or from any other text.

A review paper to start with is here.

Faheim Bacchus' has a good course, linked here.

The link to some previous offering of this course. Has changed considerably.

The four components of the course: Lectures, Software usage, Self-study, Implementation-projects (see the syllabus)

Lecture topics:
Basic examples of CSP, e.g., map coloring, N-queens etc. Related lecture slides are here (8/28/02).
Solving of CSP: minimal problem, backtracking, search space
Related lecture slides are here (9/03/02).
Fundamental concepts in CSP: satisfiability and consistency, k-consistency for different k values, directional arc-consistency,
Arc-consistency-x and path-consistency-x algorithms (for integer x), Other consistency algorithms
Search strategies: chronological BT, iterative broadening, forward checking, dependency-directed back-jumping
Current and advanced issues in CSP
Spatio-temporal CSP: point-based temporal reasoning, algebraic concepts, Allen's interval algebra, Ligozat's Cardinal algebra, Mitra's Star-algebra, Region Connection Calculi series

Acknowledgement: Some lecture notes are originally prepared by Hyoung Rae Kim.

Some suggested projects:

(1) Join Kim in experimenting with search algorithms
(2) Air trafiic control as a dynamic CSP
(3) Symmetry in CSP
(4) Learn and use EcLIPSE software

Home works will possibly be from the problems in the CSPlib

Some Works from Fall 2002

Students and their tentative interests:

Peter Engrand: Related to model-based diagnosis

Raghunath Vemuri: Neighborhood interchangability in CSP solutions

Lajos Nagy: A spatio-temporal scheduling problem using Eclipse(tm)

Weijian Chai: On GUI development using Condotta's rectangle algebra

Gaurav Tandon: Anomaly detection problem as a CSP



Home Work 1

Presentation schedule.

------------ Materials are copyrighted to me (year 2007). E-mail: