Multicriteria Optimization Problem on Prefractal Graph

Abstract

Even among single-criteria discrete problems, there are NP-hard ones. Multicriteria problems on graphs in many cases become intractable. Currently, priority is given to the study of applied multicriteria problems with specific criteria; there is no classification of criteria according to their type and content. There are few studies with fuzzy criteria, both weight and topological. Little attention is paid to the stability of solutions, and this is necessary when modeling real processes due to their dynamism. It is also necessary to study the behavior of solution sets for various general and individual problems. The theory of multicriteria optimization is a rather young branch of science and requires the development of not only particular methods, but also the construction of a methodological basis. This is also true in terms of discrete graph-theoretic optimization. In this paper, we propose to get acquainted with multicriteria problems for a special class of prefractal graphs. Modeling natural objects or processes using graphs often involves weighting edges with many numbers. The author proposes a general formulation of a multicriteria problem on a multi-weighted prefractal graph; defines three sets of alternatives—Pareto, complete and lexicographic; and proposes a classification of individual problems according to the set of feasible solutions. As an example, we consider an individual problem of placing a multiple center with two types of weight criteria and two types of topological ones. An algorithm with estimates of all criteria of the problem is proposed.

Keywords

• multicriteria problem
• prefractal graph
• set of alternatives
• algorithm with estimates