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 |
12-14 |
U140 |
16,18-20 |
|
Common |
I |
Tuesday |
16-18 |
U20 |
18 |
|
Common |
I |
Friday |
08-10 |
U20 |
15-17,20-22 |
|
H1 |
TE |
Tuesday |
10-12 |
U146 |
13,15-23 |
|
H1 |
TL |
Thursday |
10-12 |
IMADA Terminalrum |
13,15 |
|
H1 |
TE |
Thursday |
10-12 |
U147 |
17,19,21-23 |
|
H2 |
TE |
Monday |
14-16 |
U24 |
13,16-21 |
|
H2 |
TE |
Monday |
14-16 |
U145 |
23 |
|
H2 |
TE |
Wednesday |
16-18 |
U24 |
15,22 |
|
H2 |
TE |
Thursday |
10-12 |
U24 |
17 |
|
H2 |
TE |
Thursday |
10-12 |
U49 |
19 |
|
H2 |
TE |
Thursday |
10-12 |
U154 |
21-23 |
|
H2 |
TL |
Friday |
10-12 |
IMADA Terminalrum |
13,15 |
|
O1 |
TE |
Monday |
08-10 |
U147 |
17,19,21,23 |
|
O1 |
TE |
Tuesday |
14-16 |
U146 |
13,15-23 |
|
O1 |
TL |
Thursday |
14-16 |
IMADA Terminalrum |
13,15 |
|
O1 |
TE |
Thursday |
08-10 |
U147 |
22 |
|
Show entire timetable
Show personal time table for this course.
Comment:
Samlæser med DM554.
Prerequisites:
None
Academic preconditions:
The content of the course MM505 Linear algebra and the course DM507 Algorithms and Data Structures must be known.
Course introductionThe 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 outcomeAfter 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 overviewThe 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.
LiteratureMeddeles ved kursets start.
Website
This course uses
e-learn (blackboard).
Prerequisites for participating in the exam
None
Assessment and marking:
- Written exam, 4 hours. Danish 7 mark scale, external examiner.
- 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.