DM871: Linear and Integer Programming

Study Board of Science

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

STADS ID (UVA): N340030101
ECTS value: 5

Date of Approval: 11-10-2021


Duration: 1 semester

Version: Approved - active

Comment

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

The course is co-read with: DM545: Linear and integer programming (5 ECTS)
The course is optional for the following curricula: Computer Science, Applied Mathematics, Mathematics.

Entry requirements

The course cannot be followed if you have passed either DM545 or DM559, or if you have either DM545 or DM559 mandatory in your curriculum.

Academic preconditions

Students taking the course are expected to: 

  • Have knowledge of the content of the course: DM507, "Algorithms and Data Structures" or acquiring this knowledge at the same time as the course runs
  • Have knowledge of Linear Algebra 
  • Be able to program

Course introduction

Linear and Integer programming is a field at the intersection between mathematics and computer science that has seen a huge development in the last 60 years. It provides the tools that are at the core of operations research, the discipline that provides analytical methods to aid decision making. The main focus of linear and integer programming is on resource constrained optimization problems that can be described by means of linear inequalities and a linear objective function. These problems may arise in all contexts of decision making, such as manufacturing, logistics, health care, education, finance, energy supply and many others. The subject of the course therefore has an enormous practical relevance.  

The aim of the course is to enable the student to use mathematical modeling for solving practical optimization problems and to work with a mathematical software system for finding numerical solutions to the applications proposed. To reach these goals the course will provide to the student knowledge on the basics of linear programming and duality theory and on the main solution techniques for linear and integer programming, such as the simplex method, branch and bound and cutting planes. 

The course builds on the knowledge acquired in the course DM507, "Algorithms and Data Structures" 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, Applied Mathematics and others. 

In relation to the competence profile of the degree it is the explicit focus of the course to:
  • Give the competence to handle complex and development-oriented situations in academic and work settings 
  • Give skills to describe, analyze and solve mathematical problems with the application of methods and modeling formalisms from the areas of mathematics and computer science 
  • Give skills to take and justify decisions on a mathematical basis 
  • Give skills to describe, formulate and communicate problems and results to either peers and non-specialists or partners and users
  • Give knowledge and understanding of how certain optimization problems can be solved by means of linear and integer programming
  • Give knowledge of how to understand and reflect on theories, methods and practices in a specific area of mathematics

Expected learning outcome

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

  • formulate a mathematical (linear) model from a given problem description in words.
  • derive the dual program of a given linear program.
  • apply the simplex method to simple linear programs.
  • apply the branch and bound technique to small example problems.
  • derive Gomory cuts and apply the cutting plane algorithm in small example problems.
  • apply the theory from the course to practical optimization problems such as flows in networks, matching problems, packing problems, simple scheduling problems etc.
  • use computer software for solving linear and integer programs.
  • think innovative by seeing possibilities for applying theoretical knowledge in the industry.

Content

The following main topics are contained in the course:
  • Linear programming and the simplex method
  • Duality theory
  • Integer programming: branch and bound and cutting plane algorithms 
  • Min cost flow problem and its applications
  • 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

Compulsory assignments in the form of short-answer tests that are made during the course.

EKA

N340030102

Censorship

Second examiner: External

Grading

7-point grading scale

Identification

Student Identification Card

Language

Normally, the same as teaching language

Examination aids

Allowed, a closer description of the exam rules will be posted in itslearning.

ECTS value

5

Additional information

All tests during the classes must be attended. Tests during the course may be in the form of 24-hour take-home assignments or exam hours in the classroom. The schedules will be agreed with the participants.

The examination form for re-examination may be different from the exam form at the regular exam.

Indicative number of lessons

50 hours per semester

Teaching Method

At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.
Teaching activities are reflected in an estimated allocation of the workload of an average student as follows:

  • Intro phase (lectures, class lessons) - 32 hours
  • Training phase: 18 hours

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.

Educational activities 

  • Reading from text books
  • Solving homeworks
  • Applying acquired knowledge to practical projects

Teacher responsible

Name E-mail Department
Marco Chiarandini marco@imada.sdu.dk Institut for Matematik og Datalogi, Datalogi, Datavidenskab & Statistik

Timetable

25
Monday
20-06-2022
Tuesday
21-06-2022
Wednesday
22-06-2022
Thursday
23-06-2022
Friday
24-06-2022
08 - 09
09 - 10
10 - 11
11 - 12
12 - 13
13 - 14
14 - 15
15 - 16
Show full time table

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

Recommended course of study

Profile Programme Semester 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.