Abstract. A method of cutting off vertices of the graph of permutation polyhedron for solving linear conditional optimization problems on permutations is proposed. The concepts of the permutation graph of a polyhedron and a partial graph of the set of permutations are introduced. The numerical experiments based on the created software implementation of the algorithm are described.

Keywords: set of permutations, permutation polyhedron graph, method of cutting graph vertices, linear optimization on permutations.