Optimization

2022/2023
Programme:
Practical Mathematics
Year:
3 year
Semester:
first
Kind:
mandatory
ECTS:
7
Language:
slovenian
Hours per week – 1. semester:
Lectures
3
Seminar
0
Tutorial
3
Lab
0
Content (Syllabus outline)

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.

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]
Sandi Klavžar:
KLAVŽAR, Sandi, RAHBARNIA, Freydoon, TAVAKOLI, Mostafa. Some binary products and integer linear programming for k-metric dimension of graphs. Applied mathematics and computation. [Print ed.]. Nov. 2021, vol. 409, art. 126420 (7 str.). [COBISS-SI-ID 69333507]
HOLUB, Přemysl, JAKOVAC, Marko, KLAVŽAR, Sandi. S-packing chromatic vertex-critical graphs. Discrete applied mathematics. [Print ed.]. Oct. 2020, vol. 285, str. 119-127. [COBISS-SI-ID 19477507]
DEUTSCH, Emeric, KLAVŽAR, Sandi. M-polynomial revisited: Bethe cacti and an extension of Gutman's approach. Journal of Applied Mathematics and Computing. International Journal. June 2019, vol. 60, iss. 1-2, str. 253-264. [COBISS-SI-ID 18626905]
HINZ, Andreas M., KLAVŽAR, Sandi, PETR, Ciril. The Tower of Hanoi - Myths and Maths. 2nd ed. Cham: Birkhäuser, cop. 2018. XVIII, 458 str. [COBISS-SI-ID 18363737]
KLAVŽAR, Sandi, MANUEL, Paul. Strong geodetic problem in grid like architectures. Bulletin of the Malaysian Mathematical Sciences Society. July 2018, vol. 41, iss. 3, str. 1671-1680. [COBISS-SI-ID 18387033]
KLAVŽAR, Sandi, MA, Meijie. Average distance, surface area, and other structural properties of exchanged hypercubes. The journal of supercomputing. 2014, vol. 69, no. 1, str. 306-317. [COBISS-SI-ID 17064793]