COURSE UNIT TITLE

: CONSTRAINT PROGRAMMING

Description of Individual Course Units

Course Unit Code Course Unit Title Type Of Course D U L ECTS
BIL 3122 CONSTRAINT PROGRAMMING ELECTIVE 3 0 0 5

Offered By

Computer Science

Level of Course Unit

First Cycle Programmes (Bachelor's Degree)

Course Coordinator

ASSOCIATE PROFESSOR ZEYNEP NIHAN BERBERLER

Offered to

Computer Science

Course Objective

This course aims to provide an introduction to a new programming paradigm based on constraints over finite domains and provide experience of how to use these methods for solving combinatorial problems. Different constraint modeling languages and programming tools will be introduced and used for modeling complex discrete optimization and combinatorial problems as constraint programs, as well as to write specific search methods.

Learning Outcomes of the Course Unit

1   Have a basic knowledge on the working principles of a generic constraint solver.
2   Model a combinatorial problem as a constraint program, using the primitive constraints of a given constraint solver.
3   Have a basic knowledge on speeding up techniques for constraint program execution, such as identifying and breaking symmetries, or filtering algorithms.
4   Have a basic knowledge on other technologies for modeling and solving combinatorial problems, such as integer linear programming and local search.
5   Use different constraint modeling languages and constraint programming tools.

Mode of Delivery

Face -to- Face

Prerequisites and Co-requisites

None

Recomended Optional Programme Components

None

Course Contents

Week Subject Description
1 Introduction to combinatorial optimization, Overview of solution techniques for combinatorial optimization problems
2 Applications of combinatorial optimization, Introduction to constraint programming, Constraint satisfaction problems in operations research IBM ILOG OPL Language and CP Solver
3 Basic concepts of Constraint Programming, Modeling a combinatorial problem using OPL - 1 Homework 1; Project topics
4 Modeling a combinatorial problem using OPL - 2 Project group formations
5 Constraint consistency and propagation - 1, Domain reduction
6 Constraint consistency and propagation -2, Backtracking search Homework 2
7 Search strategies for constraint programming, Variable and value ordering
8 Midterm exam
9 Global constraints Other modeling languages & tools (Choco, GECODE, MiniZinc, etc.)
10 Search heuristics - 1
11 Search heuristics - 2, Symmetry Homework 3
12 Optimization problems
13 Comparison of constraint programming to mixed integer programming and hybrid strategies
14 Project presentations

Recomended or Required Reading

Textbook(s): Rossi, F., Van Beek, P., Walsh, T., Handbook of Constraint Programming, Elsevier Science, New York, 2006 (ISBN: 9780080463803).
Supplementary Book(s): Marriott, K., Stuckey, P., Programming with Constraints: An Introduction, MIT Press, 1998 (ISBN: 9780262133418).
Hooker, J.N., Integrated Methods for Optimization, Springer International Series in Operations Research & Management Science, Vol. 170, 2012 (ISBN: 9781461419006).

Planned Learning Activities and Teaching Methods

The course is taught in a lecture, class presentation and discussion format. Besides the taught lecture, group presentations are to be prepared by the groups assigned and presented in a discussion session. In some weeks of the course, results of the homework given previously are discussed.

Assessment Methods

SORTING NUMBER SHORT CODE LONG CODE FORMULA
1 MTE MIDTERM EXAM
2 ASG ASSIGNMENT
3 FIN FINAL EXAM
4 FCG FINAL COURSE GRADE MTE * 0.30 + ASG * 0.30 + FIN * 0.40
5 RST RESIT
6 FCGR FINAL COURSE GRADE (RESIT) MTE * 0.30 + ASG * 0.30 + RST * 0.40


*** Resit Exam is Not Administered in Institutions Where Resit is not Applicable.

Further Notes About Assessment Methods

None

Assessment Criteria

To be announced.

Language of Instruction

Turkish

Course Policies and Rules

To be announced.

Contact Details for the Lecturer(s)

zeynep.berberler@deu.edu.tr

Office Hours

To be announced in the beginning of the semester.

Work Placement(s)

None

Workload Calculation

Activities Number Time (hours) Total Work Load (hours)
Lectures 13 3 39
Preparations before/after weekly lectures 13 2 26
Preparation for final exam 1 15 15
Preparing assignments 3 5 15
Project Preparation 1 30 30
Preparing presentations 1 5 5
Final 1 2 2
TOTAL WORKLOAD (hours) 132

Contribution of Learning Outcomes to Programme Outcomes

PO/LOPO.1PO.2PO.3PO.4PO.5PO.6PO.7PO.8PO.9PO.10PO.11PO.12PO.13
LO.1545354
LO.245455
LO.35545553455
LO.454433554
LO.54555554555