Search course

Use the search function to find more information about the study programmes and courses available at Chalmers. When there is a course homepage, a house symbol is shown that leads to this page.

Graduate courses

Departments' graduate courses for PhD-students.

​​​​
​​

Syllabus for

Academic year
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

MPENM ENGINEERING MATHEMATICS AND COMPUTATIONAL SCIENCE, MSC PROGR, Year 1 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (compulsory 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.


Page manager Published: Thu 04 Feb 2021.