NOPT042 Constraint programming

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

• Github repository for the tutorial
• Homework assignments on Github Classroom:
  • test assignment (not graded)
  • Homework 1: leaves (due date extended by one week, until 2pm on Oct 14)
  • Homework 2: crypt-arithmetic (due date 2pm on Oct 14)
  • Homework 3: boardomino (due date 2pm on Oct 21)
  • Homework 4: knapsack (due date 2pm on Nov 4)
  • Homework 5: stable-marriage (due date 2pm on Nov 11)
  • Homework 6: moving (due date 2pm on Nov 18)
  • Homework 7: feast (due date 2pm on Nov 25)
  • Homework 8: routing (due date 2pm on Dec 2)
  • Homework 9: life (due date 2pm on Dec 9)
  • Homework 10: golfers (due date 2pm on Dec 16)
  • Homework 11: triangle (due date 2pm on Jan 6)
  • Homework 12: farmer (due date 2pm on Jan 13)
  • Additional homework assignments for extra points: packing, mcsp, digest, hanoi (due by end of March)

Tutorial schedule

Before the first tutorial

• Install Picat and try it out. (See Getting started with Picat.)
• Solve the test assignment. Push your solution to the repo, and check if it passed the tests.

1st tutorial (Sep 30)

• Program: Overview of Picat.
• Homework: leaves

2nd tutorial (Oct 7)

• Program: Intro to CP.
• Homework: crypt-arithmetic

3rd tutorial (Oct 14)

• Program: Improving models, symmetry breaking, solvers.
• Homework: boardomino

4th tutorial (Oct 21)

• Program: Search space, search strategies.
• Homework: knapsack - due on Nov 4 (Oct 28 is a national holiday)

5th tutorial (Nov 4)

• Program: Dual modeling, channeling. Assignment.
• Homework: stable-marriage due on Nov 11

6th tutorial (Nov 11)

• Program: Modeling functions. Scheduling, the cummulative constraint
• Homework: moving due on Nov 18

7th tutorial (Nov 18)

• Program: Rostering
• Homework: feast due Nov 25

8th tutorial (Nov 25 )

• Program: Routing
• Homework: routing due Dec 2

9th tutorial (Dec 2)

• Program: Implicit constraints
• Homework: life due Dec 9

10th tutorial (Dec 9)

• Program: Modeling with sets
• Homework: golfers due Dec 16

11th tutorial (Dec 16)

• Program: Tabling
• Homework: triangle due Jan 6

12th tutorial (Jan 6)

• Program: Planning
• Homework: farmer due Jan 13
• Additional homework problems: packing, mcsp, digest, hanoi due end of March

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

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.

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.