Syllabus for |
|
TMA521 - Large scale optimization
|
|
Syllabus adopted 2015-02-16 by Head of Programme (or corresponding) |
Owner: MPENM |
|
7,5 Credits |
Grading: TH - Five, Four, Three, Not passed |
Education cycle: Second-cycle |
Major subject: Mathematics
|
Department: 11 - MATHEMATICAL SCIENCES
|
This course round is cancelled. This course round is given every other year. Is not given 2015/2016
Teaching language: English
Open for exchange students
Course module |
|
Credit distribution |
|
Examination dates |
Sp1 |
Sp2 |
Sp3 |
Sp4 |
Summer course |
No Sp |
0197 |
Examination |
7,5 c |
Grading: TH |
|
|
|
7,5 c
|
|
|
|
|
|
In programs
TKITE SOFTWARE ENGINEERING, Year 3 (compulsory elective)
MPENM ENGINEERING MATHEMATICS AND COMPUTATIONAL SCIENCE, MSC PROGR, Year 1 (elective)
Examiner:
Professor
Michael Patriksson
Biträdande professor
Ann-Brith Strömberg
Go to Course Homepage
Eligibility:
In order to be eligible for a second cycle course the applicant needs to fulfil the general and specific entry requirements of the programme that owns the course. (If the second cycle course is owned by a first cycle programme, second cycle entry requirements apply.)
Exemption from the eligibility requirement:
Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling these requirements.
Course specific prerequisites
Basic courses on linear and discrete optimization
Recommendation: TMA947 Nonlinear optimization.
Aim
The purpose of the course is to provide the students with an overview of
the most important principles for the efficient solution of practial
large-scale optimization problems, from modelling to method
implementation. After a series of lectures the course work is concentrated
on project work, by which the students will apply the knowledge gained to
efficiently solve some relevant problems.
Learning outcomes (after completion of the course the student should be able to)
To analyze and suggest method principles for a variety of optimization problems, and have suffient background knowledge in order to utilize them successfully in practice through the use of optimization software tools.
Content
Large scale optimization problem almost always have some inherent structures that can - and should - be exploited in order to solve such problems efficiently. The course deals with some such principles through which large scale optimization problems can be attacked. A common term for such techniques is decomposition-coordination; convexity theory and duality underlies much of its development. Parts of this material is covered in the course Nonlinear optimization (TMA947) but are here studied in more depth.
The course includes three practical moments: an exercise in the modelling and solution of a design problem, and two project assignments where large scale optimization problems are to be solved through the use of duality theory and techniques presented during the lectures.
Contents in brief: complexity, unimodularity and convexity, minimal spanning trees, knapsack problems, location problem, generalized assignment, travelling salesman problem, network design, set covering. Decomposition/coordination, restriction, projection, variable fixing, neighbourhoods, relaxations (Lagrange), linearization, line search, coordinating master problem. Cutting planes, Lagrangian heuristics, column generation, Dantzig-Wolfe decomposition, Benders decomposition, local search, modern tree search methods.
Organisation
Lectures. A modelling exercise including including oral presentations/discussions. Two project assignments including oral and written presentations and oppositions.
Literature
See the course home page.
Examination
Written reports and oral presentations of the projects, opposition; an oral examination for a grade higher than pass.