Hulianytskyi L. Development of models and approximate methods of combinatorial optimization and their application in information technologies

The thesis is devoted to the problems of development, substantiation and approbation of the new mathematical models and methods used to solve combinatorial optimization problems, design of information technologies and tools for decisions making support and optimization in the presence of finite set of alternatives, and also of application of the developed facilities in different application domains. To solve a wide set of combinatorial optimization problems, the accelerated probabilistic modeling method (G-algorithm), which belongs to the class of stochastic local search methods, and the method of distorting polyhedrons, that follows original strategy of global search in space of candidate solutions, are proposed. On the basis of combination of advantages of the developed algorithms, new hybrid (metaheuristic) combinatorial optimization algorithms are proposed. The terms of their efficient implementation both on computers with traditional architecture and on multiprocessor computing systems are studied. The theoretical conclusions are confirmed by the conducted computing experiments. New mathematical models for the set of applied optimization problems are developed. A new technology for solving problems of optimum choice on the basis of the use of expert group judgments is proposed and substantiated. Approach used to increase intelligence level of discrete optimization systems and in a number of the applied optimization systems, is developed. Being based on the developed models and methods, the technology for responsible decision support on the basis of modeling and forecasting of key macroeconomic indicators is proposed and implemented. Keywords: combinatorial optimization, approximation algorithms, hybrid algorithms, parallel computing, allocation, investment, optimization of networks, information technologies, support of making and optimization of decisions, problem of choice, system of discrete optimization, macroeconomic forecasting.