Lobachevsky University scientists in search of fast algorithms for discrete optimization

08 December 2017

Lobachevsky University scientists are implementing a research project "Algorithmic, Complex and Structural Problems of Graph Theory and Discrete Optimization". 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 an optimal variant from a limited (but sometimes a very large) set of options. 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.

Discrete optimization problems include, for example, problems on graphs. In mathematics, a graph is an object consisting of points (called nodes or vertices of a graph) and lines (called arcs or edges) that connect some of these points. For example, with the help of a graph it is possible to depict a network of roads between cities. Then the cities will be represented by graph nodes, and the roads between them will be arcs. A graph can represent a computer local area network or even the entire worldwide web, the Internet.

In this case, computers will be the nodes of the graph, and only those nodes will be connected by an arc for which the corresponding computers are connected. To deliver a message from one computer to another, one needs to determine the shortest path between them. With the help of graphs, it is possible to depict social networks. Each node will correspond to a specific user of the social network, and two nodes will only be connected by an arc when two persons are friends.

Integer linear programming is a convenient and sufficiently universal language for describing discrete optimization problems (including problems on graphs).

During more than half a century of research in different countries of the world, fast algorithms (i.e., algorithms whose operation time is limited by a polynomial from the length of the input information) have been found for a number of discrete optimization problems.

Polynomially solvable problems include, for example, problems about the shortest path in a graph, the maximum flow, the largest matching, etc. However, no fast algorithms could be found for a large proportion of such problems, despite the efforts of thousands of experts.

Despite all efforts of a host of experts, all the improvements to algorithms for such intractable, "hard" problems differ little from direct exhaustive search. Such hard problems include, for example, the problems of a clique, the minimal covering, the maximum independent set, and many others. Thus, the question remains whether there exist in principle fast algorithms for "insolvable" problems or such effective algorithms are yet to be found? Most experts are inclined to believe that there are no such algorithms for most unsolvable problems, so no one will ever be able to find them.

Proving the well-known hypothesis "P ? NP" will mean that this is really the case. The problem "P = NP?" was formulated in 1971 by S. Cook, but so far no one has proved that P = NP or P ? NP. This is one of the most important open problems in theoretical computer science. In 2000, the Clay Mathematics Institute named it among the seven outstanding Millennium Prize Problems.

The problem of constructing polynomial algorithms and the problem of studying the effective solvability boundary give rise to a number of complex mathematical problems, and a team of the UNN researchers is currently working to solve them.

These problems include the study of the intersection of an integer lattice with a polyhedron, in particular, the description of the faces of the convex hull of this intersection; the study of boundary classes of graphs; increasing graphs; constructing effective algorithms and corresponding lower bounds for solving a number of problems (for example, the problems of an independent set, covering, packing) on graph classes; constructing effective algorithms for solving discrete optimization problems (for example, minimizing quasiconvex functions on an integer lattice), etc.