lunduniversity.lu.se

Details for Course FMAP05F Linear and Combinatorial Optimization

General
• FMAP05F
• Temporary
Course Name
• Linear and Combinatorial Optimization
Course Extent
• 7.5
Type of Instruction
• Course given jointly for second and third cycle
• 7151 (Centre of Mathematical Sciences / Mathematics)
• 2022-11-23
• Maria Sandsten

Current Established Course Syllabus

General
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 PhD 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 PhD student develop their ability to solve problems, with and without the use of a computer, and their ability to read mathematical texts.
Contents
• Linear programming. Integer programming. Transport problems. Assignment problems. Maximal flow. Some modern methods in combinatorial optimization. Algorithm complexity.
Knowledge and Understanding
• For a passing grade the doctoral student must
• understand and be able to clearly explain the theory behind the simplex method.
be able to describe and explain the mathematical theory behind some central algorithms in combinatorial optimization.
Competences and Skills
• For a passing grade the doctoral 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.
Judgement and Approach
• For a passing grade the doctoral student must
Types of Instruction
• Lectures
• Seminars
Examination Formats
• Written assignments
• Assignments.
• Failed, pass
Assumed Prior Knowledge
• FMAB20 Linear Algebra. Programming with Python or Matlab. Some course in mathematics beyond calculus in several variables (for mathematical maturity).
Selection Criteria
Literature
•
• Kolman, B. & Beck, R.E.: Elementary Linear Programming with Applications. Academic Press, 1995, ISBN: 0-12-417910. Available as E-book from the Maths Library.
Supplementary material.
B.Korte & J. Vygen: Combinatorial Optimization, Theory and Algorithms. Springer, 2019, ISBN: 9783662585665. Sixth edition. An earlier edition is available as e-book from the Mathematics Library.
Further Information
Course code
• FMAP05F
• 2022-11-23
• Maria Sandsten

All Established Course Syllabi

1 course syllabus.

Valid from First hand in Second hand in Established
Autumn 2022 2022‑11‑16 11:35:41 2022‑11‑17 09:34:24 2022‑11‑23

Current or Upcoming Published Course Occasion

No matching course occasion was found.

All Published Course Occasions

No matching course occasions were found.

0 course occasions.