Types of optimization problems. Local search.
Linear programming, standard form, conversions.
Simplex method, basic step, initial feasible solution, finiteness of the method, geometric interpretation.
Duality in linear programming, weak and strong duality.
Matrix games.
Transshipment problem, integer solutions. Maximum flow problem. Ford-Fulkerson algorithm. Max-flow min-cut theorem. Matchings and vertex covers in bipartite graphs. Job scheduling and Hungarian method.
Optimization 1
2022/2023
Programme:
Mathematics, First Cycle
Year:
3 year
Semester:
first
Kind:
optional
Group:
B2
ECTS:
5
Language:
slovenian
Course director:
Lecturer (contact person):
Hours per week – 1. semester:
Lectures
2
Seminar
0
Tutorial
2
Lab
0
Content (Syllabus outline)
Readings
V. Chvátal: Linear Programming, Freeman, New York, 1983.
B. H. Korte, J. Vygen: Combinatorial Optimization : Theory and Algorithms, 3. izdaja, Springer, Berlin, 2006.
R. J. Vanderbei: Linear Programming : Foundations and Extensions, 2. izdaja, Kluwer, Boston, 2001.
Objectives and competences
Students get familiar with the concept of optimization problem, learns how to formulate problems which appear in practice as optimization problems and learns in detail how to solve linear optimization problems.
Intended learning outcomes
Knowledge and understanding: Using a mathematical model a student can describe well a variety of problems from real life. The emphasis is on the problems that lead to linear models. Students get familiar with basic approaches for efficient solving of the obtained optimization problems.
Application: Solving real-life optimization problems.
Reflection: A meaning of presentation of practical problems in a formalized form for efficient and correct solving.
Transferable skills: Modeling of problems from practice in the form of mathematical optimization problems, ability to distinguish between computationally manageable and unmanageable problems.
Learning and teaching methods
Lectures, exercises, homework, consultations
Assessment
2 midterm exams instead of written exam, written exam
Oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)
Lecturer's references
Riste Škrekovski:
GREGOR, Petr, ŠKREKOVSKI, Riste. Long cycles in hypercubes with distant faulty vertices. Discrete mathematics and theoretical computer science, ISSN 1365-8050, 2009, vol. 11, no. 1, str. 185-198. [COBISS-SI-ID 15521113]
ŠKREKOVSKI, Riste. A Grötzsch-type theorem for list colourings with impropriety one. Combinatorics, probability & computing, ISSN 0963-5483, 1999, let. 8, št. 5, str. 493-507. [COBISS-SI-ID 9275225]
DIMITROV, Darko, DVOŘÁK, Tomáš, GREGOR, Petr, ŠKREKOVSKI, Riste. Gray codes avoiding matchings. Discrete mathematics and theoretical computer science, ISSN 1365-8050, 2009, vol. 11, no. 2, str. 123-148. [COBISS-SI-ID 15521369]
Arjana Žitnik:
MILANIČ, Martin, PISANSKI, Tomaž, ŽITNIK, Arjana. Dilation coefficient, plane-width, and resolution coefficient of graphs. Monatshefte für Mathematik, ISSN 0026-9255, 2013, vol. 170, no. 2, str. 179-193. [COBISS-SI-ID 1024499540]
PISANSKI, Tomaž, ŽITNIK, Arjana. Representing graphs and maps. V: BEINEKE, Lowell W. (ur.), WILSON, Robin J. (ur.). Topics in topological graph theory, (Encyclopedia of mathematics and its applications, ISSN 0953-4806, 128). Cambridge [etc.]: Cambridge University Press, cop. 2009, str. 151-180. [COBISS-SI-ID 15227481]
ŽITNIK, Arjana. Series parallel extensions of plane graphs to dual-eulerian graphs. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2007, vol. 307, iss. 3-5, str. 633-640. [COBISS-SI-ID 14183769]
