1. General Information

Prereq: CSCE 421/821: Foundations of Constraint Processing.

Course description: This course is a continuation of the course on Foundations of Constraint Processing (CSCE 421/821). It is intended for students with some sophistication and considerable interest in exploring methods for designing and using algorithms useful for solving combinatorial problems. The goal of the course is to study, analyzem and critique basic and current research papers. Projects are optional. Topics may include (and are not restricted to):

• Temporal reasoning,
• Symmetry and interchangeability,
• Spatial reasoning,
• Continuous CSPs,
• Distributed constraint satisfaction,
• Global constraints,
• Boolean SAT solving,
• Soft constraints,
• OR Methods in CP,
• etc.

Lectures: Mondays and Wednesdays, from 3:30 p.m. to 4:45 p.m.
Location: Avery Hall, Room 109.

Make-up Class: To be scheduled as necessary

Instructor:   Prof.  Berthe Y. Choueiry
      Office location: Room 360, Avery Hall,
      choueiry AT cse.unl.edu, tel: (402)472-5444.
      Office hours: Wednesdays/Fridays 1:30 p.m.-2:30 p.m. or by appointment.

Textbooks (check the bookstore):

• Required: Constraints Processing, Rina Dechter, Morgan Kauffman, 2003.
• Required: Handbook of Constraint Programming, Rossi et al., Editors, Elsevier, 2006.
• Papers are available from the UNL libraries (electronic resources, Math Library, etc.).

2. Contact Us

For a quick response, please use Piazza for all communications.

You may also choose to drop a note in the Anonymous Suggestion Box

3. Protocol of the Course

Format

• Study of selective chapters of the Handbook of Constraint Programming by Rossi et al.
• Study of selective chapters of the book Constraint Processing by Rina Dechter.
• Discussions of technical papers.
• Collaboration and discussion within and outside the classroom strongly encouraged unless specified (e.g., for occasional assignments, quizzes, or riddles).

Workload

• Required and recommended reading (as indicated in the Class schedule)
• Occasionally, programming, theoretical, and library-search assignments.
• An in-class presentation by a student (the speaker).
• A class discussion of the student's presentation: minimum of two comments/questions by each other student in class.
• Evaluation of the student's presentation by each other student in the class.
• Scribing of the student's presentation and the class discussion by another student in the class (the scribe).
• Evaluation of the scribe's notes by each other student in the class.

Surprise quizzes

Tests

Attendance

• Attendance is mandatory. Only three absences, with advanced notification, are allowed. Missing more than three lectures may be a cause for failing the course.
• Students are responsible for the material covered and announcements (such as lists of terms for glossary) made during the class.
• Also, there will be surprise quizzes during the regular class.
• Bonuses will be awarded to students who attend all lectures, interact lively, and participate in discussion in class.

Alerts

• Some communications with the class will be carried over email. It is the students responsibility to ensure that their email account on cse.unl.edu is working properly.
• Discussions among students and with instructor are encouraged. Homework however are a strictly individual activity: no sharing is permitted (unless when specified by instructor). Unethical behavior will be heavily sanctioned (e.g., a null grade on the task).
• Always acknowledge any help received from other individuals.
• Always fully reference material used (e.g., encyclopedia, book, paper, journal, web site).

4. Grading Policy

Grade Distribution

• Presentation of a research paper by a student: 20%. Grade will be given by instructor taking into account class evaluation.
• Scribing of a discussion or a paper presentation: 5%. A student takes notes of an entire presentation and the discussion of a topic. (Potentially, one student helps the scribe for 2%.) The class criticizes and rates the notes of the scribe. Grade will be given by instructor taking into account class evaluation.
• A critical summary of a research paper: 5%.
• Evaluation of each student presentation and each scribe notes: +1%. A non-informative evaluation is graded 0%. Failure to submit an evaluation in time is penalized with -1%.
• Project (programming): 30%
• Term paper: 25%.
• One optional exam: 25%.

• Surprise quizzes (mainly) and assignments (minimal): 10%.
• Class interaction and participation in discussions are (subjectively) evaluated for 5% of the total grade.

Grade Conversion

How to Secure a Good Final Grade

• Attendance: A bonus will be awarded to students who attend all lectures.
• Additional work: Closely monitor your grade. If you feel that your grade is slipping, contact the instructor immediately. We may be able to assign to you an additional task to put you back on the right track.

4. References

Main publication venues

• View the AAAI Digital Library.
• Conferences: Constraint Programming (CP), AAAI (online proceedings), IJCAI (online proceedings), ECAI, FLAIRS, etc.
  
• Journals: AI Journal (index at the Love Library), Constraints (index at the Love Library, online access).

Books on Reserve at the Math Library in Avery:

• Constraint Processing, Rina Dechter
• Foundations of Constraint Satisfaction by Edward Tsang.
• Many other AI books.

Online Resources:

• Puzzles: Interactive Minesweeper and Interactive Sudoku Solver.
• Benchmark Problems: The list of benchmark problems usually used in the CP Solvers programming competetion. Check also the related tools.
• Archives and On-Line Systems
• A list of Constraint Solvers
• Pointers to various generators from the ConSystlab web page.
• Various models of random generators in Java by Bart Craenen
• The ECLiPSe Constraint Logic Programming System
• Random generator in C at LIRMM
• Random generator in Common Lisp by Patrick Prosser
• Random generator in C courtesy of Fahiem Bacchus (and P. van Run).
• JACK: a library providing constraint programming and search for Java (high-level language, generic search engine, and a visualization tool).
• Association for Constraint Programming (ACP).
• Yahoo Group: Constraints, Association for Constraint Programming
• AI Topics of the American Association for Artificial Intelligence

Courses

• Constraint Networks by Rina Dechter.
• Constraint Programming Approach to AI Applications, by Michela Milano
• Foundations of Constraint Satisfaction, ESSLI 2002, by Roman Barak
• Constraint Programming: online textbook by Roman Barták.
• Reasoning Methods in AI (CS329A, CS227): courses by Pandu Nayak.
• Constraint Satisfaction Problems (CSC2512F): course by Fahiem Bacchus
• Tutorial on Constraint Programming, by Barbara Smith.
• Lecture notes by David McAllester.
• Bacchus' Constraint Programming Bibliography

Academic Research Groups & Research Centers

• Constraint Systems Laboratory at UNL
• LIA@EPFL
• APES Group in the UK. (Now defunct.)
• Cork Constraint Computation Center (4C) of Freuder in University College Cork, Ireland.
  
• Microsoft Research (Cambridge)
• Monterey Bay Aquarium Research Institute
• Palo Alto Research Center (PARC)
• NASA Ames Research Center
• (to be completed)

Industrial companies and start-ups

Latex Resources

• From Joel Gompert: Getting memory-efficient, pretty-looking, robust graphics with very fancy robust labels into LaTeX
• From Ryan Lim: The not so short introduction to LaTex2x