A Graph-Theoretic Approach to Multiobjective Permutation-Based Optimization

A Generalized Coordinate Method (GCM) for linear permutation-based optimization is presented as a generalization of the Modified Coordinate Localization Method and Modified Coordinate Method is presented, and its applications to multiobjective linear optimization on permutations are outlined. The method is based on properties of linear function on a transposition graph, a decomposition of the graph, and extracting from it a multidimensional grid graph, where a directed search of an optimal solution is performed. Depending on the search parameters, GCM yields an exact or approximate solution to the original problem. An illustrative example is given for the method.