DM841: Heuristics and Constraint Programming for Discrete Optimization

Comment

The course is offered as required and is not necessarily offered every year.
Exam attempts for DM841 are offered in accordance to the following plan, when the course is offered: ordinary Exam (January), first reexamination (March) and 2nd reexamination (June or August).

The course cannot be chosen if you have passed, registered, or have followed AI505, or if AI505 is a constituent part of your Curriculum.

Entry requirements

None

Academic preconditions

Students taking the course are expected to:

Be able to use algorithms and data structures
Be able to assess the complexity of algorithms with respect to runtime and space consumption
Be able to program

Course introduction

The aim of the course is to enable the student to solve in practice discrete optimization problems, which is important in regard to designing high efficiency solutions for industrial applications like scheduling, logistics, energy planning, sport planning, etc. Discrete optimization is an exciting scientific field that focuses with problems that are most often very difficult to solve. Constraint Programming and Heuristics are two general-purpose solution paradigms. Constraint Programming is a programming paradigm, wherein variables and constraints between variables are expressed in a declarative form. A solution is then searched by tentatively assigning a value chosen from a valid domain to a variable and by consequently filtering according to the constraints the domains of the remaining variables.

General heuristics and metaheuristics are loosely defined rules to proceed to near-optimal solutions. They are often inspired by nature. For example, local search techniques are based on the principle of trial and error, which is a possible way in which humans intuitively solve a problem. The success of specific heuristics to solve satisfactorily concrete problems relies on insights into the structure of the problem and on the possibility of an efficient implementation.

Theory and practice go hand to hand in a course on discrete optimization that aims at preparing the students to solve real-life problems. Therefore the course will provide first-hand experience through programming tasks that involve the use of tools illustrating the fundamental concepts covered in the lectures.

The course provides a basis for a master thesis in discrete optimization.

Expected learning outcome

The learning objective of the course is that the student demonstrates the ability to:

model a problem similar in nature to the ones seen in the course within the framework of constraint programming and local search;
argue about the different modeling choices arising from the theory behind the components of constraint programming, including global constraints, propagators, search and branching schemes;
develop a solution prototype in a constraint programming system;
design specialized versions of general purpose heuristics: construction heuristics and local search;
develop in a programming language a solution prototype based on heuristic algorithms;
undertake an experimental analysis, report the results and draw sound conclusions based on them;
describe the work done in an appropriate language, eventually including pseudocode.

Content

The following main topics are contained in the course:

Introduction to discrete optimization;
Modeling in constraint programming with integer and set variables;
Notions of local consistency;
Global constraints and filtering algorithms
Search;
Symmetry breaking;
Construction heuristics and greedy algorithms;
Local search: modeling and algorithms;
Metaheuristics (variable neighborhood search, tabu search, simulated annealing, iterated local search, evolutionary algorithms, ant colony optimization);
Large scale neighborhood search;
Methods for the experimental analysis of optimization algorithms;
Applications: constraint satisfaction, satisfiability, travelling salesman, vehicle routing, graph coloring, sport scheduling, scheduling, timetabling.

Literature

See itslearning for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

Autumn

Tests

Mandatory assignments

EKA

N340104102

Assessment

Second examiner: Internal

Grading

7-point grading scale

Identification

Full name and SDU username

Language

Normally, the same as teaching language

Examination aids

All common aids allowed

ECTS value

Additional information

The exam consisting of five assignments in form of small problem solving projects with practical solution and short report. Assignments one, two and four are for feedback only, assignments three and five are weighted equally in the final 7-grade scale evaluation.

The examination form for re-examination is the same form as the ordinary exam. Submitted elements from the ordinary exam can be included in the re-exam.

Indicative number of lessons

88 hours per semester

Teaching Method

Planned lessons:

Total number of planned lessons: 88

Hereof:

Common lessons in classroom/auditorium: 88

In the common lessons, concepts, theories and models are introduced and put into perspective. In these lessons there is room for questions and discussions. In addition, students will work in small groups on data-based problems and discussion topics, related to the content of the previous lessons. In these hours there is a possibility of working specifically with selected difficult concepts.

Other planned teaching activities:

Applications of the acquired knowledge to practical projects
Reading of scientific articles and book chapter
Practical experiments with the methods introduced in the course

Teacher responsible

Name	E-mail	Department
Marco Chiarandini	marco@imada.sdu.dk	Data Science

Timetable

Odense

Show full time table

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Registration

NAT

Offered in

Odense

Recommended course of study

Profile	Education	Semester	Offer period

Transition rules

Transitional arrangements describe how a course replaces another course when changes are made to the course of study.

If a transitional arrangement has been made for a course, it will be stated in the list.

See transitional arrangements for all courses at the Faculty of Science.