DM545: Linear and integer programming

The Study Board for Science

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

STADS ID (UVA): N330047101
ECTS value: 5

Date of Approval: 07-04-2025


Duration: 1 semester

Version: Approved - active

Comment

The course is co-read with DM871: Linear and Integer Programming (5 ECTS).
The course is optional for the following Bachelor study programs:Computer Science, Applied Mathematics, Mathematics.
Data Science students are referred to DM871.

Entry requirements

The course cannot be followed if you have passed DM559 (archived, offered last time, Spring 2018) or DM871, or if you have DM559 or DM871 mandatory in your curriculum.

Academic preconditions

Students taking the course are expected to: 
  • Have knowledge of Linear Algebra, eg having attended DM561, MM505, MM538 or DS827
  • Be able to program, eg having attended DM536, DM550, DM574, DS800 or DS831

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 help making better decisions. 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. 

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

Autumn

Tests

Mandatory assignment

EKA

N330047102

Assessment

Second examiner: Internal

Grading

7-point grading scale

Identification

Full name and SDU username

Language

Normally, the same as teaching language

Duration

One week

Examination aids

All common aids allowed

ECTS value

5

Indicative number of lessons

44 hours per semester

Teaching Method

Planned lessons: 


Total number of planned lessons: 44

Hereof: 

Common lessons in classroom: 28

Team lessons in classroom: 14


In the common lessions, concepts, theories and models are introduced and put into perspective. In the team lessons, students train their skills through exercises and dig deeper into the subject matter.


Other planned teaching activities: 

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

Teacher responsible

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

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Registration

NAT

Offered in

Odense

Recommended course of study

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.