(Created 2010-07-25.)
 LINEAR AND COMBINATORIAL OPTIMIZATION FMA240
Credits: 6. Grading scale: TH. Cycle: G2 (First Cycle). Main field: Technology. Language of instruction: The course might be given in English. Optional for: D4, D4pv, E4, E4pv, F4, F4bs, F4fm, F4pv, I4, Pi3, Pi3fm, Pi3pv. Course coordinator: Direcor of Studies Anders Holst, Anders.Holst@math.lth.se, Mathematics. Recommended prerequisits: FMA420 Linear Algebra. Assessment: Written and/or oral test, to be decided by the examiner. Computer work. Some minor projects should be completed before the exam. Further information: The course might be given in English. Home page: http://www.maths.lth.se/matematiklth/vitahyllan/vitahyllan.html.

Aim
Linear and combinatorial optimisations problems appear more and more often, in science technology and economics. 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, combinatorial methods have grown in importance. The aim of the course is to make the students aware of problems in linear and combinatorial optimisation 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 optimisation (including local search, branch and bound methods, simulated annealing, genetic optimisation, neural networks).

with and without the use of a computer, using appropriate computer packages, be able to show good ability to solve transport problems, assignment problems, minimal cut and maximal flow problems.

Skills and abilities
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 and (iii) choose an appropriate method to solve them.

be able to write computer programs to solve linear and combinatorial optimisation 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 optimisation.

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

Literature
Kolman, B. - Beck, R.E.: Elementary Linear Programming with Applications.
Acdemic Press 1995. ISBN 0-12-417910.
Some supplementary material.
There might be a change of course book.