(Created 2011-09-01.)

LINEAR AND COMBINATORIAL OPTIMIZATION | FMA240 |

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

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

*Skills and abilities*

For a passing grade the student must

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.

**Contents**

Linear programming. Transport problems. Maximal flow. Local search. Simulated annealing. Genetic optimization. Neural networks.

**Literature**

Holmberg, K., Optimering: metoder, modeller och teori för linjära, olinjära och kombinatoriska problem. Liber 2010. ISBN 978-91-47-09935-1

Alternative text in English:

Papadimitrou, C.H. & Steiglitz, K: Combinatorial optimization: Algorithms and complexity, Dover 2000. ISBN 978-0486402581. (May be changed.)