The Department of Numerical Mathematics and Optimization is concerned with the following research areas:
- Spectral graph theory
- Combinatorial optimization
- Numerical methods for solving partial differential equations
- Optimization in functional spaces, optimal control, convex optimization
Numerous real-life problems can be formulated as optimization problems. Solving them is of great importance for ensuring or improving the efficiency of complex real-life systems. For example, when it comes to the economy, saving resources or reducing costs has a direct impact on increasing the profitability of a company. For this reason, the development of adequate mathemetical models and adequate methods for solving a wide range of optimization problems is of great practical importance. Therefore, the interest of researchers in this area is constantly growing, which is reflected in the number of published papers dealing with optimization problems and solution methods.
Optimization methods can be divided into two large classes: exact and approximate. Exact methods guarantee optimality, but are quite demanding when it comes to execution time, while approximate methods can efficiently provide solutions to the considered in problem with a certain accuracy (optimal solutions are often reached). Many optimization problems (especially the discrete and global optimization problems) are highly coplex to solve, i.e., belong to the class of NP-hard problems. The number of local optimums can grow exponentialy with the increase of the dimension of the problem. Such problems are very difficult to solve because classical approaches that offer a guarantee of finding the true global optimum take unacceptably too much time, and often get stuck in one of the local optimums, even for the small problem dimensions. Therefore, the development and implementation of adequate approximate methods is of great practical importance. The development of computer platforms in the past decedaces has made it possible to solve many NP-hard problems by approximate methods with satisfactory accuracy.
Metaheuristics are one of the classes of approximate optimization methods, which are based on efficient procedures for finding high-quality (preferably optimal) solutions of the considered problem. The main advantage of metaheuristics is that, through a finite set of steps, they lead to good solutions to problems in a relatively short time. Metaheuristics are based on general principles, which enables their application to a larger number of optimization problems. Metaheuristic methods provide general ideas and techniques that could be applied to a large number of optimization problems Every step in a metacheuristic approach should be adjusted to a specific problem that is to be solved. The main task is to find balance between two processes: local improvement of a solution and some diversification technique that should provide that different parts of a search space are visited and also help escaping from the local optimums that are not global. Although metaheuristics often reach optimal solutions to the problem they are applied to, but their drawback is that optimality cannot be proven. Since metaheuristics are the most efficient, and often the only way to solve large-scale optimization problems, a lot of attention is paid to their development and improvement.
Scientific research work at the Department in this area is directed towards solving discrete optimization problems, optimization on graphs, as well as continuous global optimization when a large number of local optima make these problems difficult to solve. The most used metaheuristics in research are Genetic Algorithms, Variable Environment Method and its variants, GRASP, particle swarm optimization, bee colony optimization, etc. Also, research includes combining (hybridization) exact methods with metaheuristics, as well as combining two or more metaheuristic methods with methods in the form of hybrid metaheuristics.
Metaheuristics at the Department are studied and applied by prof. dr Zorica Stanimirović, prof. dr Milan Dražić, prof. dr Aleksandar Savić, dr Zorica Dražić i Kristina Kostić.
Research work in this area has been supported by the Ministry of Education, Science and Technological Development, within several project cycles: project no. 174010 Mathematical models and optimization methods of large systems (2011-2019), project no. 144007 Mathematical models and optimization methods with applications (2006-2010), project no. 1583 Mathematical models and optimization methods with applications (2002-2005),...
Spectral graph theory
In the Spectral theory of graphs, the structural properties of graphs are studied through the scope of their spectra, characteristic polynomials and eigenspaces. The advantage of this approach is reflected in the fact that the spectrum of a graph is calculable in a polynomial time, while many structural invariants are not.
Scientific research in this area is oriented to the study of spectra of regular graphs, bipartite graphs and graphs with specific structural properties. Some particular topics are: graphs with a relatively small or large number of eigenvalues, spectra of oriented graphs, spectra of signed graphs or hypergraphs. One segment of research is oriented to applications of this theory in Computer science, Chemistry, Control theory and related disciplines.
As a significant part of the research, there is an intensive international collaboration that includes research visits to universities in Germany and Portugal, participation in a large number of scientific meetings, and a joint researches with more than 30 mathematicians from more than 15 countries.
The researcher who investigates in this field is prof. dr Zoran Stanić.
Research work in this area is supported by the Ministry of Education, Science and Technological Development within several scientific projects and by several foreign scientific institutions. The list of projects can be found at this page.
Combinatorial optimization is a mathematical discipline concerned with finding extreme values of a function defined on a discrete set. For a given finite or countably infinite discrete set and a given function, the task is to find the minimum of the function on this set. In this way, a number of problems in different fields can be represented. In mathematics, problems in combinatorics, graph theory, and logic can be modeled. Important applications can also be found in resource management, production management, planning problems, location problems, etc. More recently, combinatorial optimization has proven useful for the study of algorithms of particular relevance to artificial intelligence, machine learning, operations research, and computer networks. The best known example of a combinatorial optimization problem is the traveling salesman problem.
For combinatorial optimization problems with a finite set, there are always complete search algorithms, but when the number of elements of the set under consideration is large, a complete search is not possible. In this case, specialized algorithms or various approximation algorithms must be applied. From the point of view of computer science, combinatorial optimization attempts to improve an algorithm using mathematical methods to either reduce the size of the set under consideration or to speed up the search itself. The goal of combinatorial optimization is to develop efficient algorithms for solving complex problems. When there is no effective exact method for a given problem, an approximate solution is sought using appropriate approximation methods (approximation algorithms, heuristics, metaheuristics).
Research in this area includes the analysis of specific real-world problems, the formulation of new or the improvement of existing mathematical models that adequately describe the problem in question, and the design and implementation of exact, approximate, or hybrid methods for its effective solution.
Research in this area has been supported for years by the Ministry of Education, Science and Technological Development through several project cycles: Project No. 174033 Graph Theory and Mathematical Programming with Applications in Chemistry and Computer Science (2011-2019), Project No. 174010 Mathematical Models and Methods of Optimization of Large Systems, (2011-2019), Project No. 144015 Graph Theory and Mathematical Programming with Applications in Chemistry and Technical Sciences (2006-2010), Project No. 144007 Mathematical Models and Optimization Methods with Applications (2006-2010), Project No. 1583 Mathematical Models and Optimization Methods with Applications (2002-2005).
The faculty members involved in this area are prof. dr Zorica Stanimirović, prof. dr Zoran Stanić, prof. dr Milan Dražić, prof. dr Aleksandar Savić, dr Zorica Dražić i Kristina Kostić.
Numerical methods for solving partial differential equations
Partial differential equations are ubiquitous in mathematically oriented scientific fields such as physics and engineering. These equations describe natural processes mathematically so that their solutions make physical sense. For example, they are the basis for modern research into the propagation of sound and heat propagation, for the description of diffusion, electromagnetism, electrostatics, fluid dynamics, and the like. Only in very simple cases their solutions can be found explicitly, so numerical methods are the main tool for their solution. Most often, initial and initial-boundary problems for these equations are studied. In addition, partial differential equations with fractional order derivatives also receive considerable attention. Dealing with such equations requires knowledge of the basics of fractional calculus theory. The fractional order derivatives are operators with a nonlocal character, so the equations in which they appear describe processes with a memory effect characteristic of viscoelastic materials and anomalous diffusion processes.
The scientific research work in this area focuses on the analysis and approximation of ordinary and fractional partial differential equations with and without interfaces (singular coefficients and transmission problems). The analysis includes the study of the properties of the analytical solution and the a priori evaluation in the corresponding functional spaces. The approximation is performed by the finite difference method. The stability, convergence and speed of the proposed differential schemes are evaluated as a function of the smoothness of the input data.
The faculty members involved in this area are dr Aleksandra Delić, dr Sandra Živanović i Jelena Tasić.
The research in this area is supported by the Ministry of Education, Science and Technological Development under the project Approximation of integral and differential operators and applications, 174015.
Optimization in functional spaces, optimal control, convex optimization
The research work of the chair in the field of optimization in functional spaces is mainly focused on the study and obtaining necessary and sufficient optimality conditions for various classes of optimal control problems and continuous-time programming problems with different types of phase constraints. The above problems describe mathematically natural processes in physics, mechanical engineering, aeronautics, space, economics, and robotics. Therefore, they are an important area in modern research. Also, the problems of multi-objective optimization in functional spaces with different types of solutions are studied with additional assumptions of convexity and generalized convexity. In addition, suitable dual models and methods for solving the above problems are investigated.
The researcher who investigates in this field is dr Aleksandar Jović.
Approximation of Integral and Differential Operators and Applications, 174015, Integrability and Extreme Problems in Mechanics, Geometry and Combinatorics, 7744592- MEGIC