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  
Storskalig optimering
 
Syllabus adopted 2019-02-26 by Head of Programme (or corresponding)
Owner: MPENM
7,5 Credits
Grading: TH - Five, Four, Three, Fail
Education cycle: Second-cycle
Major subject: Mathematics
Department: 11 - MATHEMATICAL SCIENCES

The course is full. For waiting list, please contact the director of studies: fridaje@chalmers.se
Teaching language: English
Application code: 20112
Open for exchange students: Yes

Module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 Summer course No Sp
0197 Examination 7,5 c Grading: TH   7,5 c   Contact examiner,  Contact examiner,  Contact examiner

In programs

MPENM ENGINEERING MATHEMATICS AND COMPUTATIONAL SCIENCE, MSC PROGR, Year 2 (elective)
MPENM ENGINEERING MATHEMATICS AND COMPUTATIONAL SCIENCE, MSC PROGR, Year 1 (compulsory elective)
MPDSC DATA SCIENCE AND AI, MSC PROGR, Year 1 (compulsory elective)
TKITE SOFTWARE ENGINEERING, Year 2 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (elective)

Examiner:

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)

  • independently analyze and suggest modelling and solution principles for a variety of optimization problems;
  • have sufficient knowledge to use these principles 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 a number of such principles through which large scale optimization problems can be attacked. A common term for such techniques is decomposition-coordination; convexity and duality theory 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 in which 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 problems, generalized assignment, travelling salesperson problem, network design, set covering problems. Decomposition/coordination, restriction, projection, variable fixing, neighbourhoods, (Lagrange)relaxation, 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 and discussions. Two project assignments including oral and written presentations and oppositions.

Literature

See the course home page.

Examination including compulsory elements

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.