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

STADS: 15001501

Level
Bachelor course

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

Teacher responsible
Email: jbj@imada.sdu.dk

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

Comment:
Ubegrænset deltagerantal

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. 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, transportation problems, 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, primal dual algorithms, 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:
Written exam, 4 hours. Danish 7 mark scale, external examiner.
Examination only after the course has been taught. Examination in oppositional terms only after approval of the Study Board

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.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.