NOPT042 Constraint programming (Fall 2023)
In the tutorial we will be modeling constraint problems in the logic-based multi-paradigm language Picat
(Pattern-matching,
Intuitive,
Constraints,
Actors,
Tabling).
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 and GitHub
Homework assignments will be posted in ReCodEx. The deadlines will be set to the beginning of the next tutorial, unless stated otherwise. Materials from the tutorial are posted below as PDFs. The source codes and live notebooks are available on GitHub.
Tutorial schedule
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 2)
- Program: Overview of Picat.
- Notebook: tutorial1.pdf
- Homework: Leaves (deadline extended by one week, until 2pm on Oct 16)
2nd tutorial (Oct 9)
- Program: Intro to CP.
- Notebook: tutorial2.pdf
- Homework: Crypt-arithmetic
3rd tutorial (Oct 16)
- Program: Improving models, symmetry breaking, solvers.
- Notebook: tutorial3.pdf
- Homework: Boardomino
4th tutorial (Oct 23)
- Program: Search space, search strategies.
- Notebook: tutorial4.pdf
- Homework: Knapsack
5th tutorial (Oct 30)
- Program: Dual modeling, channeling. Assignment.
- Notebook: tutorial5.pdf
- Homework: Stable marriage
6th tutorial (Nov 6)
- Program: Modeling functions. Scheduling, the cummulative constraint
- Notebook: tutorial6.pdf
- Homework: Moving
7th tutorial (Nov 13)
8th tutorial (Nov 20)
9th tutorial (Nov 27)
- Program: Implicit constraints
- Notebook: tutorial9.pdf
- Homework: Life
10th tutorial (Dec 4)
- Program: Modeling with sets
- Notebook: tutorial10.pdf
- Homework: Golfers
11th tutorial (Dec 11)
12th tutorial (Dec 18)
13th tutorial (Jan 8)
- Program: Homework help
- Additional homework problems: Packing, MCSP, Digest, Hanoi (due end of March)
Resources
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.