Course syllabus

# Linjär och kombinatorisk optimering

Linear and Combinatorial Optimization

## FMAF35, 6 credits, G2 (First Cycle)

## General Information

## Aim

## Learning outcomes

## Contents

## Examination details

## Admission

## Reading list

## Contact and other information

Linear and Combinatorial Optimization

Valid for: 2017/18

Decided by: PLED F/Pi

Date of Decision: 2017-04-06

Main field: Technology.

Elective for: BME4, C4-pv, D4-pv, E4, F4-pv, F4-bs, F4-bg, Pi3-pv, Pi4-bg

Language of instruction: The course will be given in English on demand

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 this,
the importance of combinatorial methods has grown. The aim of the
course is to make the students aware of problems in linear and
combinatorial optimization which are important in the applications,
and to give them knowledge about 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.

Knowledge and understanding

For a passing grade the student must

- understand and be able to clearly explain the theory behind the simplex method.
- be able to describe and informally explain the mathematical theory behind central algorithms in combinatorial optimization (including local search, branch and bound methods, simulated annealing, genetic optimization, neural networks).

Competences and skills

For a passing grade the student must

- be able to show a good capability to (i) identify problems in the area, (ii) formulate these in mathematical terms, (iii) choose an appropriate method to solve them, and finally (iv) carry out the solution, possibly with the help of a computer.
- be able to write computer programs to solve linear and combinatorial optimization problems.
- with proper terminology, in a well structured way and with clear logic be able to explain the solution to a problem within linear and combinatorial optimization.

Linear programming. Integer programming. Transport problems. Assignment problems. Maximal flow. Local search. Simulated annealing. Genetic optimization. Neural networks. Dynamic programming. Algorithm complexity.

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

Assessment: Written and/or oral test, to be decided by the examiner. Computer sessions. Some minor projects should be completed before the exam.

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.

Parts

Code: 0117. Name: Examination.

Credits: 6. Grading scale: TH.

Code: 0217. Name: Computer Exercises.

Credits: 0. Grading scale: UG.

Required prior knowledge: FMAB20 Linear Algebra.

The number of participants is limited to: No

The course overlaps following course/s: FMA240

- Holmberg, K.: Optimering, Metoder, modeller och teori för linjära, olinjära och kombinatoriska problem. Liber, 2010, ISBN: 978-91-47-09935-1.
- Kolman, B. & Beck, R.E.: Elementary Linear Programming with Applications. Academic Press, 1995, ISBN: 0-12-417910. Alternative in English.
- Supplementary material.

Course coordinator: Studierektor Anders Holst, Studierektor@math.lth.se

Teacher: Sara Maad Sasane, sara@maths.lth.se

Course homepage: http://www.ctr.maths.lu.se/course/linkombopt/