DM559: Linear and Integer Programming (7.5 ECTS)

STADS: 15018001

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.

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

Prerequisites:
None

Academic preconditions:
The content of the course DM507 Algorithms and Data Structures assumed known.

Course introduction
Linear and Integer programming is a field at the intersection between mathematics and computer science that has seen a huge development in the last 60 years. It provides the tools that are at the core of operations research, the discipline that provides analytical methods to help making better decisions. The main focus of linear and integer programming is on resource constrained optimization problems that can be described by means of linear inequalities and a linear objective function. These problems may arise in all contexts of decision making, such as manufacturing, logistics, health care, education, finance, energy supply and many others. The subject of the course therefore has an enormous practical relevance. The course will first introduce the elements of linear algebra that are relevant for computer science and especially for linear and integer programming. Then it will focus on the basics of linear programming and duality theory. Finally, it will present the main solution techniques, such as the simplex method, branch and bound and cutting planes. Besides presenting the theory and teach skills in mathematical modeling, the course primarily has a practical aim. It deals with algorithms and applications and it includes the use a mathematical software system to find numerical solutions to the problems proposed.

Qualifications

• Ability to model mathematically resource constrained optimization problems and solving them by means of a mathematical software system.

Expected learning outcome
At the end of the course the student is expected to be able to:

• make calculations in matrix algebra.
• solve systems of linear equations both manually and with the computer.
• apply linear algebra to solve practical problems that resemble those treated in the course.
• 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 branch and bound technique to small example problems.
• derive Gomory cuts and apply the cutting plane algorithm in small example problems.
• apply the theory from the course to practical optimization problems such as flows in networks, matching problems, packing problems, simple scheduling problems etc.
• use computer software for solving linear and integer programs.
• think innovative by seeing possibilities for applying theoretical knowledge in the industry.

Subject overview
Matrix algebra, systems of linear equations, rank of matrices, Gauss elimination, matrix inversion, vector spaces, linear transformations, inner products, the simplex method, the duality theorem, network flows, integer programming, methods for solving integer programs, branch and bound, relaxation, linear models. Practice on 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
Mandatory assignments. Is evaluated internal on a pass/fail basis by the teacher.

Assessment and marking:

1. 4 hours written exam. Evaluated by external censorship by the Danish 7-mark scale.

Reexamination in the same exam period or immediately thereafter. The reexam is an oral exam, evaluated by the Danish 7-mark scale and external censorship.

Expected working hours
The teaching method is based on three phase model.
Intro phase: 44 hours
Skills training phase: 50 hours, hereof:
 - Tutorials: 42 hours
 - Laboratory exercises: 8 hours

Educational activities Study phase: 30 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.