Mathematical modeling of optimization problems Field of study: Computer Science
Programme code: W4-S2IN19.2020

Module name: Mathematical modeling of optimization problems
Module code: W4-IN-S2-20-3-MMPO
Programme code: W4-S2IN19.2020
Semester: summer semester 2021/2022
Language of instruction: Polish
Form of verification: course work
ECTS credits: 3
Description:
This subject aims at the exact and effective solving of intractable optimization problems. The students are familiarizing with the following three approaches: (i) lineasr and integer programming (for example MathProg language), (ii) satisfiability modulo theories (for example based on Z3 library), and (iii) answer set programming (for example AnsProlog). Thanks to that every student should know all aspects of using classical and modern exact optimization 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]
Is able to use selected programming libraries in order to formulate combinatorial optimization problems as a linear program (also integer program). [M_001]
 K_U01 [1/5] K_U05 [1/5] K_U08 [3/5] K_U09 [3/5]
Is able to solve an combinatorial optimization task using modern search nethods, 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]
Has knowledge about formulating combinatorial optimization tasks by means of the classical and modern methods of mathematical modeling. [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
Midterm for lecture [W_001]
Executing assignments that involve all approaches descibed in the lecture.
 M_003
Midterm for lab [W_002]
Programming assignments that involve classical and modern combinatorial optimization problems, with the help of glpk and Z3 libraries as well as 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]
Oral presentation with the help of prepared slides. Focusing on the hard part of the topics, giving basic examples and suggesting web pages for more advanced ones.
 15
Familiarizing with the topics, appropriate software, selected web pages, and recommended literature.
 30 Midterm for lecture [W_001]
laboratory classes [Z_002]
Preparing students for executing assignments by showing the methodology and handling steps.
 15
Writting computer programs and the analysis of existing solutions on the Internet.
 30 Midterm for lab [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)