PSU CS 443/543: Combinatorial Search

Winter 2012

Instructor: Bart Massey
Time: Monday and Wednesday 1640-1830
Place: Neuberger Hall (NH) 47
CRN: 45392 (443), 45393 (543)

(This is a tentative syllabus, and will change frequently and without notice throughout the course.)

Combinatorial search, also known as state-space search, is a way of solving apparently intractable problems by considering a large number of possible solutions in a plausible order.

This course teaches how to perform a state-space search, and how to apply state-space search to real-world problems.

Course Schedule

Week 1: Introduction to Search

  • Monday 9 Jan: Course mechanics, goals; What is state space search?
  • Wednesday 11 Jan: Problem statements; Basic search techniques
  • Reading: [intro]
  • Homework 1: TotallyNuts

Week 2: Foundations

  • Monday 16 Jan: Martin Luther King Jr. Day—University Closed
  • Wednesday 18 Jan: SAT and NP Completeness
  • Reading: [np1]

Week 3: Constraint Satisfaction Problems

  • Monday 23 Jan: Intro to CSPs
  • Wednesday 25 Jan: Simple complete search for CSPs
  • Reading: [cl], [focs] Ch. 1

Week 4: Depth-First Search

  • Monday 30 Jan: Introduction to depth-first search
  • Wednesday 1 Feb: Advanced depth-first search
  • Reading: [focs] Ch. 2, 5

Week 5: Best-First Search

  • Monday 6 Feb: Best-first for CSPs
  • Wednesday 8 Feb: Pathfinding search
  • Reading: [ckk]
  • Homework 2: Tents

Week 6: Local Search

  • Monday 13 Feb: Introduction to local search
  • Wednesday 15 Feb: Improving local search
  • Reading: [focs] Ch. 8
  • Project: Job Shop Scheduling

Week 7: Advanced Search

  • Monday 20 Feb: Optimization
  • Wednesday 22 Feb: Hybrid search
  • Reading: [swo], [focs] Ch. 10

Week 8: Pathfinding and Planning

  • Monday 27 Feb: Return to pathfinding
  • Wednesday 29 Feb: Planning
  • Reading: [warp], [hsp]

Week 9: Scheduling

  • Monday 5 Mar: Scheduling problems
  • Wednesday 7 Mar: Scheduling search
  • Reading: [rcps]

Week 10: Final Thoughts

  • Monday 12 Mar: TBA
  • Wednesday 14 Mar: Review

Course Communication

This webpage is http://wiki.cs.pdx.edu/cs543 . The course discussion email list is mailto:cs543-winter2012@wiki.cs.pdx.edu . You are required to sign up for the email list at http://svcs.cs.pdx.edu/mailman/listinfo/cs543-winter2012 , as crucial information may be posted there and you are expected to be able to receive it.

Bibliography

  • [focs Edward Tsang, Foundations of Constraint Satisfaction, 1993.  [PDF]
  • [intro] Matt Ginsberg, Essentials of Artificial Intelligence, Chapters 2-3.  [PDF]
  • [np1] Michael Garey and David Johnson, Computers and Intractability, Chapter 2.  [PDF]
  • [cl] Peter Brucker, Scheduling Algorithms (2nd ed.), Chapter 3 Section 4.  [PDF]
  • [mcfl] Steven Minton, Mark D. Johnston, Andrew B. Philips and Philip Laird, Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems.  [PDF]
  • [rsat] Robert Bayardo and Robert Schrag, Using CSP Look-Back Techniques to Solve Real-World SAT Instances.  [PDF]
  • [swo] David Joslin and David Clements, Squeaky Wheel Optimization.  [PDF]
  • [rcps] James Crawford, An Approach To Resource-Constrained Project Scheduling.  [PDF]
  • [warp] Charles McVey, David Clements, Bart Massey and Andrew Parkes, Worldwide Aeronautical Route Planner.  [PDF]
  • [hsp] Blai Bonet and H├ęctor Geffner, Planning as heuristic search.  [PDF]
  • [ckk] Richard E. Korf, A complete anytime algorithm for number partitioning, Artificial Intelligence 106:181-203 1998.  [PDF]

Useful Links

About the Course

The catalog says: "Explores methods for the solution of constraint satisfaction and related problems using search techniques, in the context of real-world problems such as resource-bounded scheduling, enterprise planning, classical planning, and one- and two-player games. Emphasis is on coding projects, and on reading and reporting on selected literature."

Instruction is through a series of lectures, readings, and web-based materials. Homework will consist of a sequence of programming projects, culminating in a substantial final project.

Prerequisites

Prerequisites for the course are: algorithms and data structures courses; a discrete math course; and the ability to program fluently in some reasonably efficient and clear programming language such as C, C++, Curry, Java, ML, Prolog, Scheme, Smalltalk, etc. (If you are in doubt about the appropriateness of some language for this course, please consult the instructor.)

Course Goals

  • Articulate the notion of state space and the role of state spaces in computer science.
  • Use the vocabulary of class, problem, instance, and solution in discussing computational theory.
  • Determine whether a given decision problem is in P, in NP, and/or NP hard.
  • Use understanding of combinatorial state spaces to design or select search techniques for solving instances of combinatorial problems.
  • Determine whether a problem is amenable to local search, complete search, or hybrid techniques.
  • Select knowledgeably from a wide variety of combinatorial search techniques.
  • Use boolean constraint satisfaction (SAT) instances as a theoretical tool for analysis and as an intermediate form for applying existing SAT solvers to NP-hard problems.
  • Implement combinatorial search algorithms efficiently and cleanly in a reasonable programming language.
  • Cite relevant combinatorial search literature.

Course Text

We will use Foundations of Constraint Satisfaction by Edward Tsang as our primary course text; we will cover about half of the book. This 1993 book is out of print, but Prof. Tsang has graciously allowed us to use and reproduce it for the purposes of this class.

You can download a PDF copy of the whole book from our course site (the access password will be announced in-class and on the course email list), or individual chapters from Prof. Tsang's site. Bound hardcopy will be available at the PSU Bookstore through Odin Ink for those who would like to purchase it.

Coursework

Coursework is of several kinds.

  • A gradated series of homework projects applying combinatorial search to interesting problems.
  • A final larger course project, or a take-home final exam.
  • Course grades will be at the discretion of the instructor, who will consider attendance, participation, and attitude.

Course Project

The course project will involve designing, implementing and evaluating a combinatorial search application. Wide latitude is given in selection of projects: a "standard" project has been provided for those who choose not to select their own.

Final Exam

The Final Exam for this course is now available. It is a brief take-home programming exercise to test skills learned during the course.

Homework

The homework consists mainly of programming assignments. The programming can be done in any reasonably clear and efficient programming language: many students choose C, C++, or Java, but ML, Scheme, Prolog, Smalltalk, or the like may be a better choice in many ways. (Haskell is a little weird for this course, because of the unspecified order of execution.) For unusual languages (i.e. those not installed by default in the Linux Laboratory) please contact me in advance for approval and so that I can get set up to run programs.

In general, I will ask that programs read from standard input and write to standard output, and that the programs require no options or other configuration. Please take these requirements, and all of the requirements in each assignment, seriously.

A homework submission should include

  • All source code for the program.
  • Any instructions needed to successfully build and run the program (including a Makefile if at all appropriate) on a box in the Linux Laboratory.
  • A writeup: see below. (All re-submissions should include all of these materials as well, even if they have not changed.)

The writeup is as important as the program. It should contain a description of the algorithms and design of the program, a discussion of the program's performance and notes on any issues of interest that arose during the homework. In general, the writeup should look like a scientific document. (There is a nice guide to technical writing at Columbia University: you may find it useful.) Plain ASCII text is the preferred format for writeups: if you must use some fancier format, HTML or PDF are acceptable. Proprietary formats (e.g. Word or Framemaker documents) are not acceptable and will be discarded unread.

The submission should be bundled into a tar or zip archive, including a README describing its components, that unpacks into the current directory. The archive should be e-mailed to mailto:cs543-homework@svcs.cs.pdx.edu as an attachment. The subject of the e-mail should be "CS 443/543 HW #", where "#" is the homework number.

Academic Honesty

Normal Student Conduct Code, Departmental, and University guidelines apply. Every student is encouraged to work with other students and seek outside assistance in completing the course. However, it is absolutely mandatory that any assistance received (coding help, algorithmic help, ideas, writeup, references, etc.) be acknowledged explicitly and fully by the student. Failure to do so is plagiarism, the lowest form of academic conduct, and will result in a zero on the assignment: the instructor will do everything he legally and ethically can to end the academic career of a plagiarist.

If you have doubts about the propriety of some course of academic conduct, please consult the instructor: he will be happy to advise.