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
Censorship: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Spring
STADS ID (UVA): N340032101
ECTS value: 5
Date of Approval: 29-10-2018
Duration: 1 semester
Version: Approved - active
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 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.
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
Exam element a)
Obligatory tasks in the form of small projects that are made during the course.
Second examiner: External
7-point grading scale
Full name and SDU username
Normally, the same as teaching language
To be announced during the course
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
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.
- Reading from research articles
- Solving homeworks
- Applying acquired knowledge to practical tasks