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
Show entire timetable
Show personal time table for this course.

Revison of timetable:
: Laboratorietimerne for hold S1 i DM545 om onsdagen fra kl. 12-14 i uge 17, har følgende ændringer: Lokale ændret fra til IMADA Terminalrum

Comment:
Ubegrænset deltagerantal. 4.kvartal.

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.