DM872: Mathematical Optimization at Work

The Study Board for Science

Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N340032102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn, Spring
Level: Master

STADS ID (UVA): N340032101
ECTS value: 5

Date of Approval: 09-05-2025


Duration: 1 semester

Version: Approved - active

Comment

The course is offered as needed and is not necessarily offered every year. Examination projects are offered according to the following plan when the course is offered:

    Autumn: ordinary examination (January), first re-examination (March) and 2nd re-examination in (June)
    Spring: ordinary examination (June), first re-examination (August) and 2nd re-examination in (January)

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

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. 

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.

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:
  • Branch and Cut
  • Lagrangian relaxation
  • Dantzig-Wolfe decomposition and column generation
  • Branch and Price
  • Stochastic programming
  • 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

Autumn

Tests

Obligatory tasks

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

All common aids allowed

ECTS value

5

Additional information

Examination consists of two mandatory sssignments consisting of small problem solving projects with practical solution and short report. The two projects are weighted equally.

Indicative number of lessons

48 hours per semester

Teaching Method

Planned lessons:
Total number of planned lessons: 48
Hereof:
Common lessons in classroom/auditorium: 48

Other planned teaching 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 Data Science

Additional teachers

Name E-mail Department City
Konstantin Pavlikov kop@sam.sdu.dk Institut for Virksomhedsledelse (IVL)

Timetable

Odense
Show full time table (start E24)
Show full time table (start F25)

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.