Syllabus for |
|
TMA521 - Project course in optimization |
|
Owner: TM |
|
5,0 Credits (ECTS 7,5) |
Grading: TH - Five, Four, Three, Not passed |
Level: C |
Department: 11 - MATHEMATICAL SCIENCES
|
Teaching language: English
Course module |
|
Credit distribution |
|
Examination dates |
Sp1 |
Sp2 |
Sp3 |
Sp4 |
|
No Sp |
0197 |
Examination |
5,0 c |
Grading: TH |
|
|
|
|
5,0 c
|
|
|
|
Contact examiner |
In programs
EMMAS MSc PROGR IN ENGINEERING MATHEMATICS, Year 1 (elective)
TTFYA ENGINEERING PHYSICS, Year 4 (elective)
TM Teknisk matematik, Year 2 (elective)
TITEA SOFTWARE ENGINEERING, Year 3 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING - Algorithms, Year 4 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING, Year 3 (elective)
Examiner:
Professor
Michael Patriksson
Eligibility:
For single subject courses within Chalmers programmes the same eligibility requirements apply, as to the programme(s) that the course is part of.
Course specific prerequisites
Basic knowledge of linear and discrete optimiza-tion.
Aim
The purpose of the course is to give the students insight into some of the most important principles for the efficient solution of practical, large-scale optimization problems, ranging from the modelling to the construction of solution methods. The main activity in the course is the project work, in which the students utilize these principles for the efficient solution of some relevant optimization problem.
Content
A series of lectures capture important concepts in modelling and solution of optimization problems. The purpose is to give insight in how inherent difficulties and problem structures can be identified. Utilizing this knowledge, the student can formulate an appropriate model and identify one or a number of alternative solution principles. In the second part of the course, these principles are applied to project work, where the student from a given problem description identifies a relevant modelling of the problem, structures and sound solution appro-aches, to complete with the numerical solution of some pratical problem using relevant software.
Outline of content: a selection of : I (Optimization problems): Review of linear programming, unimo-dularity and convexity, minimal spanning tree, knapsack problem, location problem, generalized assignment, travelling salesman problem, network design, route planning. II (Principles for algorithms): Decomposition/coordination, restriction, projection, variable fixing, neighbourhood, relaxations (Lag-range, SDP), linearization, line search, coordinating master problem. III (Algorithms): Cutting planes, Lagrangean heuristics, column generation, Dant-zig-Wolfe decomposition, Benders decomposition, derivative free methods, local search, meta heuristics, modern tree search methods.
Literature
S.G. Nash and A. Sofer, Linear and Nonlinear Programming, McGraw-Hill, 1996 (selection).
L.A. Wolsey, Integer Programming, Wiley, 1998 (selection).
Journal articles.
Examination
A written report and oral presentation of the project, opposition; an oral examinatin for a grade higher than pass.