Multiobjective Optimization on Permutations with Applications

A method of multiobjective optimization on permutations (MOP) is offered based on the Directed Structuring Method and using Graph Theory. Prospects of applying graph techniques are caused by representability of the feasible domain by graph vertices. It yields advantages in using traditional methods, as well as in developing new ones. Our method is a generalization of the Method for Sequential Analysis of Variants for multiobjective optimization on permutations and multi-permutations. Most problems on combinatorial configurations sets are NP-hard, and a search of an exact solution requires enumerating a factorial number of variants. To decrease it, the method includes: a choice of an unconstraint MOP method; a choice of a method for generating a sequence of feasible solutions for a constraint MOP adapted to objective function; constructing and examining a structural graph of the optimization problem; a polynomial algorithm choice for solving the problem on partially ordered vertices of the graph.