DM872: Mathematical Optimization at Work

Study Board of Science

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

STADS ID (UVA): N340032101
ECTS value: 5

Date of Approval: 29-10-2018


Duration: 1 semester

Version: Approved - active

Comment

New course Spring 2019.
The course cannot be chosen by students who: have passed DM858, DM204

Entry requirements

None

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 Blackboard 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

Censorship

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

5

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.

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

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi, fiktiv)

Team at Registration & Legality

NAT

Recommended course of study

Profile Programme Semester Period