NOPT042 Constraint programming (Fall 2024)

In the tutorial we will be modeling constraint problems in the logic-based multi-paradigm language Picat (Pattern-matching, Intuitive, Constraints, Actors, Tabling).

Office hours during the teaching period:

• Thursday 2pm in S303 (right after class)
• Troja campus: Monday 3:30pm outside of N1

or make an appointment (via email); two additional hours per week will be available.

Credit requirements

There will be 12 homework assignments each of which is worth 1 point. In order to get the credit, you must gain at least 8 points, out of which at least 4 points must be from the second half of the semester (assignments 7-). Expect increasing complexity of the assignments as the semester progresses. There will be an additional option to get at most 4 points after the end of classes for solving somewhat harder problems.

The solutions to the homework assignments must be 100% your own work. Do not discuss them with anyone but me, do not search for solutions on the internet, and do not share your code.

ReCodEx

Homework assignments will be posted in ReCodEx. The deadlines will be set to the beginning of the next tutorial, unless stated otherwise.

GitHub and Binder

The source codes and live notebooks are available on GitHub, and hosted on Binder:

• GitHub repository
• Binder docker

The individual notebooks are also posted below as PDFs and HTML slides.

Resources

• Picat homepage
• Getting started with Picat
• Constraint solving and planning with Picat
• Modeling and Solving AI Problems in Picat (tutorial by R. Barták and N. Zhou)
• CSPLib: A problem library for constraints
• Håkan Kjellerstrand’s Picat page
• The lecture by R. Barták
• Previous tutorial by R. Barták in SICStus Prolog
• Previous tutorial by me in MiniZinc

Tutorial schedule (will be updated)

Before the first tutorial

• Install Picat and try it out. (See Getting started with Picat.)
• Join our ReCodEx group.
• Solve the (ungraded) “Hello, World!” assignment.
• Let me know if you encounter any issues!

1st tutorial (Oct 3)

• Program: Overview of Picat.
• Notebook: tutorial1.ipynb (pdf, html)
• Homework: Leaves

2nd tutorial (Oct 10)

• Program: Intro to CP.
• Notebook: tutorial2.ipynb (pdf, html)
• Homework: Crypt-arithmetic

3rd tutorial (Oct 17)

• Program: Improving models, symmetry breaking, solvers.
• Notebook: tutorial3.ipynb (pdf, html)
• Homework: Boardomino

4th tutorial (Oct 24)

• Program: Search space, search strategies.
• Notebook: tutorial4.ipynb (pdf, html)
• Homework: Knapsack

5th tutorial (Oct 31)

• Program: Dual modeling, channeling. Assignment.
• Notebook: tutorial5.ipynb (pdf, html)
• Homework: Stable marriage

6th tutorial (Nov 7)

• Program: Modeling functions. Scheduling, the cummulative constraint.
• Notebook: tutorial6.ipynb (pdf, html)
• Homework: Moving

7th tutorial (Nov 14)

• Program: Rostering problems. Global constraints based on finite automata.
• Notebook: tutorial7.ipynb (pdf, html)
• Homework: Feast

8th tutorial (Nov 21)

• Program: Global constraints. Routing.
• Notebook: tutorial8.ipynb (pdf, html)
• Homework: Routing

9th tutorial (Nov 28)

• Program: Implicit constraints.
• Notebook: tutorial9.ipynb (pdf, html)
• Homework: Life

10th tutorial (Dec 5)

• Program: Modeling with sets.
• Notebook: tutorial10.ipynb (pdf, html)
• Homework: Golfers

11th tutorial (Dec 12)

• Program: Tabling with Picat.
• Notebook: tutorial11.ipynb (pdf, html)
• Homework: Triangle

12th tutorial (Dec 19)

• Program: Planning with Picat.
• Notebook: tutorial12.ipynb (pdf, html)
• Homework: Farmer

13th tutorial (Jan 9)

• Program: Q&A, Homework help
• Additional homework problems: Packing, MCSP, Digest, Hanoi (due end of March)

Frequently asked questions (FAQ)

• What should I do if I have a question? — Check the FAQ. If you don’t see the answer here email me putting “nopt042” in the subject.
• What if I want a consultation? — Talk to me after class, come to the scheduled office hours, or email me to arrange an appointment.