Olhovsky D. Exact and approximate cut-off methods for solving linear optimization problems on permutations

The dissertation suggests and explains the second combinatorial cut-off method in conventional linear problems of the vertex located sets with the exception of degeneracy in the auxiliary linear programming problems, which, unlike the first cut-off method, allows cutting-off solely on the polyhedron of permutations. We obtained the simplex shape of the reversible polyhedron, allowing to apply Karmarkar's algorithm in the combinatorial cut-off method. The dissertation devises and explains the combinatorial cut-off method based on Karmarkar's algorithm for conventional linear problems of combinatorial optimization on permutations that can take into account the properties of combinatorial sets more effectively. We have devised the approximate polynomial method of analysing the graph of reversible polyhedron with the implementation for a multiprocessor system that allows getting the approximate solution of problems in practice using the advantages of multiprocessor systems.