PA163 Constraint Programming 2024
Hana Rudová
Faculty of Infomatics, Masaryk University
July 2, 2024
Base information
Course website: interactive syllabus at IS MU
https://is.muni.cz/auth/el/fi/podzim2024/PA163/index.qwarp
slides and lecture videos added during semester
Two sample exams from the last years
Materials in Czech
lecture slides from the past years
homework examples with solutions
Final exam and homeworks: language
can be written in Czech/Slovek (English terminology must be used)
Hana Rudová, PA163, FI MU: PA163 Constraint Programming 2024 2 July 2, 2024
Evaluation
Final exam: 80 points
40 points at least
theoretical part: 55 points
overview questions, examples, comparisons, terminology, algorithms
programming part on computers: 25 points
Optimization Programming Language
2 homeworks: 20 points
8 points at least
one homework for up to 10 points
Bonus points: up to 1 points per lecture
for active participation in the lecture
responding questions, discussions including asking the questions
Total: A 90 and more, B 80-89, C 70-79, D 60-69, E 55-59
Hana Rudová, PA163, FI MU: PA163 Constraint Programming 2024 3 July 2, 2024
Literature
Dechter, R. Constraint processing. Morgan Kaufmann Publishers,
2003. http://www.ics.uci.edu/~dechter/books/
Handbook of Constraint Programming, Elsevier, 2006
Barták, R. On-line guide to constraint programming.
http://ktilinux.ms.mff.cuni.cz/~bartak/constraints/
Barták, R. Contstraint programming, course at MFF UK, Prague
(both in English and Czech).
http://kti.ms.mff.cuni.cz/~bartak/podminky/index.html
Constraint Programming online (community web)
http://www.cp-online.org/
Additional Internet resource available from the course website
Hana Rudová, PA163, FI MU: PA163 Constraint Programming 2024 4 July 2, 2024
Outline of lectures
Introduction
Arc and path consistency
Propagation for non-binary constraints
Global constraints
Directional consistency, graph width
Look-ahead algorithms, branch & bound
Look-back algorithms
Scheduling: propagation and search
Incomplete search
Local search
Hana Rudová, PA163, FI MU: PA163 Constraint Programming 2024 5 July 2, 2024
Seminars
Seminars are obligatory
One absence acceptable
Absence at two seminars: additional homeworks
Missed half (three) of the seminaries: not possible
Goals
Getting programming practice with the constraint programming
Contents
Introdution to the Optimization Programming Language (OPL)
Global constraints
Modeling
Scheduling
Search
Hana Rudová, PA163, FI MU: PA163 Constraint Programming 2024 6 July 2, 2024
Software: IBM ILOG CPLEX Optimization Studio
Download at IS MU Study Materials
MS Windows, Linux, MacOS
no-cost academic edition
free version not recommended
Software availability at FI MU
computer hall, aisa
Windows, Linux and MacOS
Optimization Programming Language (OPL)
a natural mathematical description of optimization models
high-level syntax with simpler and shorter code
for mathematical programming and constraint programming
https://www.ibm.com/analytics/optimization-modeling
Hana Rudová, PA163, FI MU: PA163 Constraint Programming 2024 7 July 2, 2024
Optimization Programming Language (OPL)
Volsay produces the compounds NH3 (ammonia) and NH4Cl (ammonium
chloride). Volsay has 50 units of nitrogen (N), 180 units of hydrogen (H)
and 40 units of chlorine (Cl).
Volsay makes a profit of 40 Eur per unit of NH3, and 50 Eur per unit of
NH4Cl sold. How does Volsay maximize profit based on inventory?
using CP;
dvar int+ nh3;
dvar int+ nh4cl;
maximize
40 * nh3 + 50 * nh4cl
subject to {
nh3 + nh4cl <= 50;
3 * nh3 + 4 * nh4cl <= 180;
nh4cl <= 40;
};
Hana Rudová, PA163, FI MU: PA163 Constraint Programming 2024 8 July 2, 2024