Optimization problems, examples.
Local optimization.
Linear programming, the standard form and conversions among different forms.
The simplex method, iteration step, initial feasible solution, termination, geometric interpretation.
The dual problem, weak and strong duality.
Matrix games.
The transshipment problem. Integer solutions.
Maximum flow problem. Ford-Fulkerson algorithm. Max-flow- min-cut theorem.
Matchings and coverings in bipartite graphs. The assignment problem and the Hungarian method.
Shortest paths in graphs. Dijkstra's algorithm. Floyd-Warshall algorithm. Application of shortest paths algorithms to practical problems such as the Chinese postman problem.
Software tools for solving optimization problems.
Optimization
2021/2022
Programme:
Practical Mathematics
Year:
3 year
Semester:
first
Kind:
mandatory
ECTS:
7
Language:
slovenian
Course director:
Lecturer (contact person):
Hours per week – 1. semester:
Lectures
3
Seminar
0
Tutorial
3
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 encounter the notion of an optimization problem and learn how to model various problems which appear in practice
as optimization problems, with emphasis on solving linear optimization problems.
Intended learning outcomes
Knowledge and understanding:
Students are able to model various problems which appear in practice accurately. The emphasis is on the problems that lead to linear models. They are familiar with the basic techniques that can be used to solve the resulting optimization problems efficiently.
Application:
Solving optimization problems which appear in practice.
Reflection:
The importance of representing practical problems in a formal way which helps to solve them efficiently and adequately.
Transferable skills:
Ability to model practical problems as mathematically formulated optimization problems, ability to distinguish between computationally feasible and infeasible problems.
Learning and teaching methods
Lectures, exercises, homeworks, consultations
Assessment
Homework 2 midterm exams instead of written exam, written exam
Oral exam
Students receive two grades: one from the written exam and homeworks, and the other from the oral exam.
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)
Lecturer's references
Sergio Cabello:
CABELLO, Sergio, DÍAZ-BÁÑEZ, José Miguel, PÉREZ LANTERO, Pablo. Covering a bichromatic point set with two disjoint monochromatic disks. Computational geometry, ISSN 0925-7721. [Print ed.], 2013, vol. 46, iss. 3, str. 203-212. [COBISS-SI-ID 16326233]
CABELLO, Sergio, GIANNOPOULOS, Panos, KNAUER, Christian, MARX, Dániel, ROTE, Günter. Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. ACM transactions on algorithms, ISSN 1549-6325, 2011, vol. 7, no. 4, article 43 (27 str.). [COBISS-SI-ID 16028761]
CABELLO, Sergio, ROTE, Günter. Obnoxious centers in graphs. SIAM journal on discrete mathematics, ISSN 0895-4801, 2010, vol. 24, no. 4, str. 1713-1730. [COBISS-SI-ID 15762265]
Emil Žagar:
JAKLIČ, Gašper, KANDUČ, Tadej, PRAPROTNIK, Selena, ŽAGAR, Emil. Energy minimizing mountain ascent. Journal of optimization theory and applications, ISSN 0022-3239, 2012, vol. 155, is. 2, str. 680-693. ,. [COBISS-SI-ID 4382935]
JAKLIČ, Gašper, ŽAGAR, Emil. Curvature variation minimizing cubic Hermite interpolants. Applied mathematics and computation, ISSN 0096-3003. [Print ed.], 2011, vol. 218, iss. 7, str. 3918-3924. [COBISS-SI-ID 16049241]
JAKLIČ, Gašper, ŽAGAR, Emil. Planar cubic G [sup] 1 interpolatory splines with small strain energy. Journal of Computational and Applied Mathematics, ISSN 0377-0427. [Print ed.], 2011, vol. 235, iss. 8, str. 2758-2765. [COBISS-SI-ID 15770969]
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]
