Mathematical modeling of optimization problems Field of study: Computer Science
Programme code: W4-S2INA19.2021

Module name: Mathematical modeling of optimization problems
Module code: W4-INA-S2-20-3-MMPO
Programme code: W4-S2INA19.2021
Semester: summer semester 2022/2023
Language of instruction: English
Form of verification: course work
ECTS credits: 3
Description:
This module aims at the exact and effective solving of intractable optimisation problems. The students get acquainted with the following three approaches: 1. Linear and integer programming (for example MathProg language) 2. Satisfiability Modulo Theories (for example based on Z3 library) 3. Answer Set Programming (for example AnsProlog) Thanks to that every student should know all aspects of using classical and modern exact optimisation methods.
Prerequisites:
(no information given)
Key reading:
1. Tommi Sottinen (2009). Operations research with GNU Linear Programming Kit. ORMS1020 course notes. Department of Mathematics and Statistics, University of Vaasa, Finland. 2. Daniel Kroening, Ofer Strichman (2016). Decision Procedures – An Algorithmic Point of View, Second Edition. Springer. 3. Vladimir Lifschitz (2019). Answer Set Programming. Springer.
Learning outcome of the module Codes of the learning outcomes of the programme to which the learning outcome of the module is related [level of competence: scale 1-5]
The student can use selected programming libraries to plan combinatorial optimisation problems as a linear programme (also integer programme). [M_001]
 K_U01 [1/5] K_U05 [1/5] K_U08 [3/5] K_U09 [3/5]
The student can solve a combinatorial optimisation task using modern search methods, such as Answer Set Programming and Satisfiability Modulo Theories, in a selected programming language. [M_002]
 K_U01 [1/5] K_U05 [3/5] K_U08 [3/5] K_U09 [3/5]
The student knows planning combinatorial optimisation tasks through classical and modern mathematical modelling methods. [M_003]
 K_W01 [4/5] K_W02 [3/5] K_W04 [1/5] K_W09 [1/5]
Type Description Codes of the learning outcomes of the module to which assessment is related
Credit for the lecture [W_001]
The student should complete the executing assignments involving all approaches described in the lectures.
 M_003
Credit for the laboratory classes [W_002]
The student should complete programming assignments that involve classical and modern combinatorial optimisation problems, with the help of glpk and Z3 libraries and AnsProlog language.
 M_001 M_002
Form of teaching Student's own work Assessment of the learning outcomes
Type Description (including teaching methods) Number of hours Description Number of hours
lecture [Z_001]
The lectures are oral presentations supported by slideshows, focusing primarily on the most demanding topics, giving basic examples and suggesting web pages for more advanced students.
 15
The students get acquainted with the topics, appropriate software, selected web pages and recommended literature.
 30 Credit for the lecture [W_001]
laboratory classes [Z_002]
The classes prepare students for executing assignments by showing the method and sequence of operations.
 15
The students write computer programmes and the analysis of existing solutions on the Internet.
 30 Credit for the laboratory classes [W_002]
Attachments
Module description (PDF)
Information concerning module syllabuses might be changed during studies.
Syllabuses (USOSweb)
Semester Module Language of instruction
(no information given)