DM872: Mathematical Optimization at Work

Entry requirements

The course cannot be chosen by students who: have passed DM858, DM204

Academic preconditions

Students taking the course are expected to:

Have knowledge of the content of the course: DM545 / DM871: Linear and Integer Programming
Be able to program

Course introduction

The course focuses on advanced solution techniques to solve the mathematical optimization problems behind a few concrete applications. The course aims at giving the theory behind the solution techniques and above all at gaining practical experience in deploying them on a few numerical instances for optimization problems taken from scheduling and vehicle routing applications. Examples of such applications are: flow shop and job shop scheduling in manufacturing, resource constrained project scheduling, crew and workforce scheduling, timetabling and vehicle routing with time windows.

The applications will be precisely stated and modeled in terms of mixed integer linear programming (MILP) problems. Due to the size of these instances basic solution techniques for MILP problems are insufficient and advanced solution techniques must be used. We will learn about Lagrangian relaxation, Dantzig Wolfe decomposition, column generation and Benders decomposition with main focus on the implementation of these techniques on the basis of a software system for MILP problems.

The course builds on the knowledge acquired in the course, "Linear and Integer Programming" and gives an academic basis for doing a master thesis project and other theoretically or practically oriented study-activities as well as for studying elective courses, that can be chosen as part of the degrees in Computer Science, Mathematics-Economics, Applied Mathematics and others.

In relation to the competence profile of the degree it is the explicit focus of the course to:

Give skills in planning and carrying out scientific projects at a high professional level including managing work-related situations that are complex, unpredictable and require new solutions
Provide skills to describe, analyze and solve advanced computational problems using the learned models
Provide skills to elucidate the advanced hypotheses on a qualified theoretical basis and to critically evaluate owns and others' research and scientific models
Provide skills in developing new variants of the methods learned where the specific problem requires it
Provide skills in communicating research-based knowledge and discuss professional and scientific problems with both peers and non-specialists
Provide expertise in a specific field of study, based on the highest international research in the fields of computer science and operations research
Provide knowledge about a variety of specialized models and methods developed in computer science and operations research based on the highest international research, including topics from the subject's research front

Expected learning outcome

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

Recognize and describe problems arising in scheduling and routing while making use of opportune formal notation.
Formulate a mathematical (linear) model from a given problem description in words.
Describe advanced solution approaches based on mixed integer linear programming.
Implement advanced solution approaches to MILP problems.
Use computer software for solving linear and integer programs.
Analyze the solution methods with respect to computation time and solution quality.
Think innovative by seeing possibilities for applying theoretical knowledge in the industry.

Content

The following main topics are contained in the course:

Dantzig-Wolfe decomposition and Benders decomposition
Column generation and Lagrangian relaxation
Crew scheduling
Vehicle routing
Software for solving linear and integer programming problems

Literature

See itslearning for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

Spring

Tests

Obligatory tasks in the form of small projects that are made during the course.

EKA

N340032102

Assessment

Second examiner: External

Grading

7-point grading scale

Identification

Full name and SDU username

Language

Normally, the same as teaching language

Examination aids

To be announced during the course

ECTS value

Additional information

All obligatory assignments during the course must be accomplished.
The examination form for re-examination may be different from the exam form at the regular exam.

Indicative number of lessons

48 hours per semester

Teaching Method

At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.

Intro phase (lectures, class lessons) - 26 hours
Training phase: 22 hours, including 22 hours tutorials

In the intro phase, concepts, theories and models are introduced and put into perspective. In the training phase, students train their skills through exercises and dig deeper into the subject matter.

Studyphase activities:

Reading from research articles
Solving homeworks
Applying acquired knowledge to practical tasks.

Teacher responsible

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

Timetable

Odense

Show full time table

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & 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.