2024 Spring 2023 Spring 2022 Spring 2021 Spring 2020 Spring 2019 Spring 2018 Spring 2017 Spring 2016 Spring 2015 Spring 2014 Spring 2013 Spring
Show the courses of study containg this course Se overgangsordninger
Dansk English

DM545: Linear and integer programming (5 ECTS)

STADS: 15012301

Level
Bachelor course

Teaching period
The course is offered in the spring semester.

Teacher responsible
Email: marco@imada.sdu.dk

Timetable
Group Type Day Time Classroom Weeks Comment
Common I Monday 14-16 U140 14-15,17,21
Common I Monday 14-16 U20 16,18-19
Common I Tuesday 12-14 U150 16
Common I Wednesday 10-12 U20 14,20
Common I Wednesday 10-12 IMADA ComputerLab 15
Common I Wednesday 10-12 U140 17
Common I Wednesday 08-10 U150 19
Common I Thursday 14-16 IMADA ComputerLab 17
Common I Thursday 08-10 U20 21
Common I Thursday 08-10 IMADA ComputerLab 21
Common I Friday 08-10 U48A 20
O1 TE Tuesday 14-16 U155 16,18
O1 TL Wednesday 14-16 U142 15,17
O1 TE Wednesday 10-12 U155 18
O1 TE Wednesday 08-10 U140 22
O1 TE Thursday 12-14 U142 14-15,17,19-21
O1 TE Thursday 12-14 U45 22
Show entire timetable
 Show personal time table for this course.

Comment:
Ubegrænset deltagerantal. Fælles undervisning med DM559 Lineær- og heltalsprogrammering.

Prerequisites:
None

Academic preconditions:
The content of the course MM505 Linear algebra and the course DM507 Algorithms and Data Structures must be known.

Course introduction

The course will introduce the theory of linear programming and duality, together with the simplex method for solving linear programming problems. It will then focus on integer linear programming and methods for solving integer linear programming problems, such as branch and bound and branch and cut. Beside methods and algorithms the course is about mathematical modelling of real-life optimization problems. The content of the course has therefore a high practical relevance.

Expected learning outcome
After taking the course the student is expected to be able 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 concept of relaxation, for example in connection with branch and bound
  • apply the theory from the course to practical optimization problems such as flows in networks, matching problems, packing problems, simple scheduling problems etc.
  • apply the branch and bound technique for solving integer programs
  • use computer software for solving linear and integer programs
Subject overview
The simplex method, the duality theorem, network flows, integer programming, methods for solving integer programs, branch and bound, relaxation, linear models. The students will also be introduced to software for solving linear and integer programs. 

Literature
    Meddeles ved kursets start.


Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
  1. Written exam, 4 hours. Danish 7 mark scale, external examiner.
  2. Obligatory project assignments. Internal examiner by teacher. Pass/fail. The projects must be passed to in order to attend the exam.

Reexamination in the same exam period or immediately thereafter. The reexam is an oral exam. Danish 7 mark scale and external examiner.



Expected working hours
The teaching method is based on three phase model.
Intro phase: 24 hours
Skills training phase: 18 hours

Educational activities Study phase: 15 hours

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.