DM515: Introduction to linear and integer programming (5 ECTS)

STADS: 15005901

Level
Bachelor course

Teaching period
The course is offered in the spring semester.
4th quarter.

Teacher responsible
Email: marco@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

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 Struchtures must be known.

Course introduction
To introduce the theory of linear programming and duality, introduce methods for solving linear programs, introduce integer programming as well as methods for solving integer programs such as branch and bound and branch and cut. The students will also acquire knowledge about the theory of linear and integer programming and will learn how to apply the theory to a number of practical problems.

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

Syllabus
See syllabus.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
a) Written exam, 4 hours. Danish 7 mark scale, external examiner.

b) Obligatory project assignments. Internal examiner by teacher. Pass/fail. The projects must be passed to in order to attend the exam.

Reexam after 2nd quarter. 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.

Forelæsninger (22 timer) og eksaminatorier/laboratorier (20 timer).
Educational activities

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.