UNN scientists in search of fast algorithms for discrete optimization
24 July 2017
The research project "Algorithmic, Complex and Structural Problems of Graph Theory and Discrete Optimization" is being implemented by Lobachevsky University scientists. At the head of the research team is Vadim Lozin, leading researcher of the UNN Institute of Information Technologies, Mathematics and Mechanics, professor of the Mathematics Institute at the University of Warwick (UK). Many important practical problems involve the need to choose the optimal variant from a limited (but sometimes a very large) set of options. Such problems are known as problems of discrete, or combinatorial, optimization. Theoretically, they could be solved by checking all the options and choosing the best one, but in practice this type of sorting is often not feasible, since it would require enormous time even on modern high-performance computers. Therefore, scientists have to look for fast algorithms that do not require exhaustive search. Such new algorithms can be successfully used in research and development of complex network structures and can find their application in telecommunications and IT, logistics, transport systems and many other fields. A convenient and sufficiently universal language for describing discrete optimization problems (including problems on graphs) is integer linear programming. During more than half a century of research in different countries of the world, fast algorithms have been found for a number of discrete optimization problems. However, no fast algorithms could be found for a large proportion of such problems, despite the efforts of thousands of experts. The team of the UNN researchers is currently working on a number of complex mathematical problems related to constructing polynomial algorithms and studying the boundary of effective solvability. This research project is supported by the Russian Science Foundation grant.