Gradinar I. Algorithms for solving some high-dimensional discrete optimization problems on graphs

The dissertation is devoted to the problems of development and improvement of algorithms for solving discrete optimization problems of the high-dimensional graphs. The mathematical model of the problem of finding the maximum ro-dense set of vertices on a graph was build, the properties of such sets used in algorithms developing were established. The equivalence of the weighted set packing problem and the problem of finding an independent set of vertices of maximum weight were established. To find the approximate solutions for high-dimensional discrete optimization problems on the graphs developed an approach based on the use of the global equilibrium search method ideas. The approximate algorithms based on this approach were developed for such classes of problems as: maximum independent set (and independent set of maximum weight) of vertices on a graph, maximum weighted set packing, maximum k-plex (co-k-plex) and maximum weighted k-plex (co-k-plex) of a graph, maximum ro-dense set of vertices on a graph, maximum weighted cut of a graph. The appropriate software based on the developed algorithms was created. The experimental research and analysis of designed and well-known algorithms, which confirmed the effectiveness of the proposed algorithms, was done. The approaches to accelerate the solution of discrete optimization problems on the high-dimensional graphs with the use of RESTART-technology and Path-relinking method were suggested.