Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Discrete and Continuous Optimization - NOPX046

Title:	Diskrétní a spojitá optimalizace
Guaranteed by:	Student Affairs Department (32-STUD)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2020
Semester:	summer
E-Credits:	6
Hours per week, examination:	summer s.:2/2, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	English
Teaching methods:	full-time
Teaching methods:	full-time
Is provided by:	NOPT046

Guarantor:	prof. Mgr. Milan Hladík, Ph.D. prof. RNDr. Martin Loebl, CSc.
Class:	Informatika Bc.
Classification:	Informatics > Optimalization
Pre-requisite :	{NXXX014, NXXX015, NXXX016, NXXX017, NXXX018, NXXX022, NXXX023, NXXX024, NXXX025, NXXX033}
Incompatibility :	NOPT046
Interchangeability :	NOPT046
Is incompatible with:	NOPT046
Is interchangeable with:	NOPT046

Opinion survey results Examination dates SS schedule Noticeboard

Annotation -

Last update: doc. Mgr. Jan Kynčl, Ph.D. (25.01.2018)

Review course covering fundamental fields of optimization, incl. computational methods. There are countless examples from almost all branches of human doing leading to problems coming under this discipline. Introduction to several other courses specialized in the solution of particular classes of optimization problems. Previous knowledge of linear programming, e.g. from NOPT048 Linear Programming and Combinatorial Optimization (formerly Optimization Methods) is advisable (but not required).

Course completion requirements -

Last update: doc. Andreas Emil Feldmann, Dr. (14.02.2018)

For the English version of the tutorial:

The tutorial will feature two quizzes, one midterm quiz on the topic of discrete optimization and one final quiz on the topic of continuous optimization. You need to obtain 60% of the total points of both quizzes to obtain the credit for the tutorial.

Literature -

Last update: prof. Mgr. Milan Hladík, Ph.D. (30.09.2021)

Electronic textbook (for the continuous part):

https://kam.mff.cuni.cz/~hladik/DSO/text_dso_en.pdf

Further references:

M.S. Bazaraa, H.D. Sherali, C.M. Shetty: Nonlinear Programming, Wiley, New Jersey, 2006.

S. Boyd, L. Vandenberghe: Convex Optimization, Cambridge University Press, 2009.

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver. Combinatorial Optimization. Wiley, New York, 1998.

Requirements to the exam -

Last update: prof. Mgr. Milan Hladík, Ph.D. (28.04.2020)

For the English version of the lecture:

To participate in the exam of the lecture you need to obtain the credit for the tutorial. The exam is semi-oral, and you have three tries.

In exceptional situations, the exam can have a distance form.

Syllabus -

Last update: doc. Andreas Emil Feldmann, Dr. (14.02.2018)

Fundamentals of discrete optimization:

Introduction, examples of optimization and examples of techniques. Analysis of algorithms, implementation and complexity.

Shortest paths and minimum spanning trees and relations.

Maximum matching and applications, relation to flows in networks. Algorithms for matchings. Postman problem.

Traveling salesman problem (TSP): heuristics, applications and relations.

Comparisons of hard and polynomial problems.

Fundamentals of continuous optimization:

Convex functions and sets

Convex optimization

Quadratic programming

Cone programming and duality

Karush-Kuhn-Tucker optimality conditions

Basic methods

Programming with uncertain data, robust optimization