Course syllabus

Linear and Combinatorial Optimization
Linjär och kombinatorisk optimering

FMAP05, 7.5 credits, A (Second Cycle)

Valid for: 2024/25
Faculty: Faculty of Engineering LTH
Decided by: PLED F/Pi
Date of Decision: 2024-04-15
Effective: 2024-05-08

General Information

Depth of study relative to the degree requirements: Second cycle, in-depth level of the course cannot be classified
Elective for: BME4, C4, D4-pv, E4, F4, F4-pv, F4-bs, Pi4-bs, Pi4-pv
Language of instruction: The course will be given in English on demand

Aim

In science, technology and economics, linear and combinatorial optimization problems appear more and more often. The most well known example is linear programming, where the so called simplex method has been of utmost importance in industry since it was invented in the middle of the 20th century. Other important problems, e.g. for effective data processing, contain discrete variables, for example integers. In connection with these, the importance of combinatorial methods has grown. The aim of the course is to make the students aware of some problems in linear and combinatorial optimization which are important in applications, and to give them knowledge about modern mathematical methods for their solution. The aim is also to make the students develop their ability to solve problems, with and without the use of a computer, and their ability to read mathematical texts.

Learning outcomes

Knowledge and understanding
For a passing grade the student must

Competences and skills
For a passing grade the student must

Contents

Linear programming. Integer programming. Transport problems. Assignment problems. Maximal flow. Some modern methods in combinatorial optimization. Algorithm complexity.

Examination details

Grading scale: TH - (U, 3, 4, 5) - (Fail, Three, Four, Five)
Assessment:

Written exam or take home exam combined with oral exam, to be decided by the examiner.

The examiner, in consultation with Disability Support Services, may deviate from the regular form of examination in order to provide a permanently disabled student with a form of examination equivalent to that of a student without a disability.

Modules
Code: 0122. Name: Linear and Combinatorial Optimization.
Credits: 7.5. Grading scale: TH - (U, 3, 4, 5).

Admission

Assumed prior knowledge: FMAB20 Linear Algebra. Programming with Python or Matlab. Some course in mathematics beyond calculus in several variables (for mathematical maturity).
The number of participants is limited to: No
Kursen överlappar följande kurser: FMA240 FMAF35

Reading list

Contact

Course coordinator: Studierektor Anders Holst, Studierektor@math.lth.se
Teacher: Stefan Diehl, Stefan.Diehl@math.lth.se
Course homepage: https://canvas.education.lu.se/courses/20371