| TAOP33 |
Combinatorial Optimization, Introductory Course, 4 ECTS credits.
/Kombinatorisk optimering gk/
For:
D
U
|
| |
Prel. scheduled
hours: 42
Rec. self-study hours: 65
|
| |
Area of Education: Science
Main field of studies: Mathematics, Applied Mathematics,
|
| |
Advancement level
(G1, G2, A): G2
|
|
Aim:
The course deals with mathematical tools for solving and analyzing
combinatorial optimization problems. Focus lies on choosing and using the most efficient algorithm for each specific problem structure.
The algorithms are suitable for implementation on computer.
After finished course, the student shall be able to:
- describe important types of combinatorial optimization problems
- formulate combinatorial optimization problems as mathematical models and determine the difficulty of the problems with the help of complexity theory
- explain the design of and the principles behind efficient solution
methods and use the methods for solving combinatorial optimization problems
- use available software for solving optimization problems
- take part of development of software for optimization
problems
- develop a simple heuristic for a structured combinatorial optimization problem
- explain and use basic concepts, such as local and global optimality, convexity, extreme point, complexity, duality, basic graph theory and branch-and-bound
|
|
Prerequisites: (valid for students admitted to programmes within which the course is offered)
Linear Algebra
Note: Admission requirements for non-programme students usually also include admission requirements for the programme and threshhold requirements for progression within the programme, or corresponding.
|
|
Organisation:
The lectures and lessons treat theory, methods and models, as well as exercises in model formulation and problem solving. The computer exercises contain both implementation of optimization algorithms and solution of combinatorial optimization problems with the help of available software.
|
|
Course contents:
Introduction to optimization, problem formulation, graphical solution,
computational complexity. The simplex method, linear duality and
sensitivity analysis. Basic graph theory, models and methods
for finding minimal spanning tree, traveling salesman tour, postman tour, shortest path, minimum cost flow and maximal flow. Methods for integer programming, such as branch-and-bound. Problem complexity, heuristics.
|
|
Course literature:
Kaj Holmberg: Optimering (Liber, 2010).
|
|
Examination: |
|
Written examination
Laboratory work
|
3 ECTS
1 ECTS
|
| |
|
|
Course language is Swedish.
Department offering the course: MAI.
Director of Studies: Ingegerd Skoglund
Examiner: Kaj Holmberg
Link to the course homepage at the department
Course Syllabus in Swedish
|