Dimensionality Reduction of the Criterion Space in Some Optimization Problems Natalia Kondruk, and Mykola Malyar Uzhhorod National University, Narodna Square, 3, Uzhhorod, 88000, Ukraine Abstract A characteristic feature of many practical decision-making tasks is their multicriteria, which leads to the complexity of information processing when finding a solution. Failure to consider many criteria can lead to inconsistency of the constructed model with the real problem and impossibility to find its solution. Therefore, improving the effectiveness of methods for solving such problems is an urgent research problem. This work is a continuation of research on the use of the clustering method based on fuzzy binary relations in solving different classes of applied problems. It is devoted to the urgent problem of increasing the efficiency of methods for solving multi-objective problems of linear programming by applying the approach of clustering the criterion space, identifying strongly dependent efficiency criteria, further reduction of the criterion space of the problem into a smaller centroid space. In this paper we analyzes the current state of research of multi-objective optimization problem. The clustering method based on fuzzy binary relations has been adapted to detect groups of vectors by angular similarity measure. At the same time, a new kind of membership function was proposed. The approach of criterion space reduction of the problem by the space of centroids is described. At the same time centroids no longer need normalization. Based on this approach, the weighted sum scalarization method in the selection of the decision maker who decides the weights of the efficiency criteria is modified. Some approaches for determining the weights of centroids representing the criteria in the respective clusters are proposed. The scheme of the complex approach to the decision of multi-objective linear optimization problem with use of the approach of criterion space reduction is presented. Keywords 1 Multicriteria, multi-objective optimization problem, weighted sum scalarization method, clustering, reduction of criterion space 1. Introduction Decision-making processes are the basis of any purposeful activity. Mathematical and information models have become widely used to describe and analyze complex technical, social, economic, medical and other systems. The real needs of the practice of designing, creating and operating complex systems require consideration and coordination of several (many) different goals. Consideration of only one criterion simplifies the real problem and leads to a wrong solution [1]. A characteristic feature of many practical problems in the study of socio-economic [2-4] systems is multicriteria, which leads to the complexity of information processing in finding a solution. An important place in solving practical problems is occupied by problem situations, which are modeled and described by linear models and depend on many factors, so solving a multicriteria decision-making problem is often accompanied by solving vector optimization problems [1-5]. Multicriteria arises when the quality of the modeling process needs to be assessed in terms of several indicators. The formation of a set of criteria is a complex multi-step iterative procedure performed by a specialist in specific (problem) areas of knowledge or together with specialists in the field of II International Scientific Symposium «Intelligent Solutions» IntSol-2021, September 28–30, 2021, Kyiv-Uzhhorod, Ukraine EMAIL: natalia.kondruk@uzhnu.edu.ua (A. 1); mykola.malyar@uzhnu.edu.ua (A. 2) ORCID: 0000-0002-9277-5131 (A. 1); 0000-0002-2544-1959 (A. 2) ©️ 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) 121 organization of decision-making processes. For example, consider the problem of economic planning, which is the basis of production management in socio-economic systems. As a rule, production planning is carried out taking into account certain criteria, which must reach extreme values with limited resources (raw materials, labor, production, time). For example, the criteria of profit, profitability, demand, gross output, load of equipment and manpower, sales - are maximized, and outlay, cost of production, costs of purchasing raw materials, the use of overtime - are minimized. There are many methods for solving multi-objective optimization problem (in short MOP). The main idea of many of them is the transition to a single-criteria task, taking into account additional information from the decision-maker (in short DM): determining the weights of performance criteria, highlighting the main criterion and certain thresholds for others, ranking criteria by priority. Obviously, such information is subjective, but directly affects the solution to the problem. Therefore, it is advisable to study and analyze the existing hidden relationships between the criteria of effectiveness and the definition of groups of similar goals, to reduce the criterion space of the problem, and only then to determine one or another method for solving it. In addition, the number of criteria also affects the complexity of decision-making problems. With a small number of criteria, the task of comparing two alternatives is quite simple and transparent, the values of the criteria can be directly compared and a preferred alternative can be worked out. With a large number of criteria, the task becomes immense for the decision maker. Sometimes, with a large number of criteria, they can usually be combined into groups that have a specific semantic meaning. These groups of criteria are usually independent. Revealing the structure on a set of criteria makes the decision-making process much more meaningful and efficient. 2. General statement of the multi-objective optimization problem Multi-objective (vector, multi-criteria, multi-purpose) optimization problem is the basis of mathematical models [2-5], which describe a socio-economic system or technical object. We formalize the description of such a model. Let 𝑥 = (𝑥𝑗 , 𝑗 = ̅̅̅̅̅ 1, 𝑛) – be a vector variables of model; 𝑛 is the number of variables (coordinates of the vector), the vector of variables belongs to the space of 𝑛 -dimensional vectors 𝑥 ∈ 𝑅𝑛 (space variables of model) and, as a rule, its integrality 𝑥 ≥ 0. The functioning of the system, the technical object is aimed at fulfilling certain goals - criteria functionally related to the vector of variables 𝑓𝑖 (𝑥), 𝑖 = ̅̅̅̅̅̅ 1, 𝑚 , 𝑚 ≥ 2, where 𝑚 – number of criteria. The set of criteria can be represented as a vector-function: (1) 𝐹 = (𝑓1 (𝑥 ), 𝑓2 (𝑥 ), … , 𝑓𝑚 (𝑥 )), which is called a vector criterion (vector objective function). 𝑓𝑖 (𝑥), 𝑖 = ̅̅̅̅̅̅ 1, 𝑚 are called partial or local criteria. The set of all criteria can be conditionally considered as some criterion space of the problem. The functional relationship of variables is established by certain relations, which are subject to restrictions: 𝑔𝑖 (𝑥 ) ≤ 𝑏𝑖 , 𝑖 = ̅̅̅̅̅ 1, 𝑘, (2) where 𝑘 – the number of constraints included in the mathematical model. Relation (2) determines the range of allowable values of variables 𝑋 ⊂ 𝑅𝑛 (space of alternatives). Each component of the vector criterion (1) is aimed at the extremum (maximization, minimization) of its value. The problem of choosing an acceptable vector of variables 𝑥 ≥ 0 from the area of restrictions (2) (𝑥𝜖 𝑋) by vector criterion 𝐹 is called a vector problem of mathematical programming or a multi-objective optimization problem (MOP). It is assumed that problem (1), (2) is convex, i.e., each coordinate of the vector criterion 𝐹 – concave function, 𝑔𝑖 (𝑥), 𝑖 = ̅̅̅̅̅ 1, 𝑘 – convex functions. The set of points that defines the range of valid values of variables 𝑋, is a nonempty set and is a compact set. It follows that there is a global solution of the multicriteria problem for each local criterion from (1). Multicriteria problem (1), (2) is considered for the case when the point of optimum 𝑥𝑖∗ , 𝑖 = ̅̅̅̅̅̅ 1, 𝑚, obtained by solving the problem for each criterion 𝑓𝑖 (𝑥), 𝑖 = ̅̅̅̅̅̅1, 𝑚 , separately, do not coincide (at 122 coincidence the decision is considered trivial). Therefore, from a mathematical point of view, problem (1), (2) is incorrect, i.e., if one of the criteria 𝑓𝑖 (𝑥), 𝑖 = ̅̅̅̅̅̅ 1, 𝑚, reached its extremum, the improvement of other components of the vector criterion is impossible. It follows that the solution of problem (1), (2) can be only some "compromise" solution that satisfies to some extent all partial criteria (1). The basic methods of solving multicriteria problems are aimed at solving this problem. The first attempt to formulate the optimality of the solution was made by V. Pareto. That is, the Pareto set is the set of feasible solutions for which it is impossible to simultaneously improve all particular efficiency criteria (i.e. improve at least one of them without worsening the rest). In multi-purpose optimization problems, the point 𝑥 ∗ ∈ 𝑋 is Pareto optimal [6] if it is valid and there is no other point 𝑥 ′ ≠ 𝑥 ∗ , for which (3) 𝑓𝑖 (𝑥 ∗ ) ≥ 𝑓𝑖 (𝑥 ′ ), ∀𝑖 = ̅̅̅̅̅̅ 1, 𝑚, for at least one criterion, a strict inequality holds. The set of such points is called the Pareto set of optimal points, or effective. They are also called the set of non-improved points, i.e., you can not find another such point from 𝑋, that some of the criteria improve and others do not deteriorate. In the general case, effective solutions are not equivalent to each other, so for two Pareto optimal solutions, one cannot say which one is better. The set of points, Pareto, lies between the points of the optimum obtained in solving problems (1), (2) separately for each partial criterion. Usually the methods of solving vector problems are built in such a way as to reach one of the Pareto optimal points, taking into account the importance (priority) of a criterion 𝑓𝑖 (𝑥) for the decision maker. The evaluation of the obtained solution is made on the basis of the evaluation vector 𝑦 ∗ = (𝑓1 (𝑥 ∗ ), 𝑓2 (𝑥 ∗ ), … , 𝑓𝑚 (𝑥 ∗ )), each coordinate of which shows the "received win" according to the corresponding partial criterion. If in problem (1), (2) the partial criteria are linear functions, and the set described by inequalities (2) is polyhedral, then such a multicriteria problem is called linear. Formally, it can be represented as: 𝑛 (4) 𝑓𝑖 (𝑥 ) = ∑ 𝑐𝑖𝑗 𝑥𝑗 → 𝑒𝑥𝑡𝑟, 𝑖 = ̅̅̅̅̅̅ 1, 𝑚, 𝑚 ≥ 2, 𝑗=1 𝑛 (5) ∑ 𝑔𝑘𝑗 𝑥𝑗 ≤ 𝑏𝑘 , 𝑘 = ̅̅̅̅̅ 1, 𝑝, 𝑗=1 𝑥𝑗 ≥ 0, 𝑗 = ̅̅̅̅̅ 1, 𝑛. (6) where (4) describes the criterion space of the problem, and (5), (6) the set of admissible solutions of the problem 𝑋. Models of linear programming occupy a significant place among the known models of socio-economic processes [2, 5]. 3. General characteristics of methods in multi-objective optimization Nowadays, quite a lot of methods have been developed to solve vector optimization problems, but they are all heuristic in nature. When developing methods for solving multipurpose problems, it is necessary to solve specific problems, which, one way or another, are related to the normalization of criteria [7], the choice of the optimality principle, which determines the rule of choosing one point from the whole Pareto set. Since particular criteria have different physical meanings, because they are measured in different units; their scale is not commensurable, so it is impossible to compare the quality of the results obtained for each criterion. The operation of bringing the scales of particular criteria to a single, usually dimensionless, is called the normalization of criteria. The choice of the principle of optimality is the main problem of vector optimization. It turns out to be difficult to formally describe the principle of optimality (criteria of "correctness of the solution"). First, the objects considered by decision theory are so diverse that it is not possible to establish uniform optimality principles for all classes of problems. Secondly, the goals of the participants in the decision- making processes are different and often opposite. Thirdly, the criteria for the correctness of the solution depend not only on the nature of the problem, its purpose, but also on how impartially they are chosen, otherwise there will be preparation for the answer. And finally, the difficulties of choosing a solution 123 can be hidden in the very formulation of the problem, if the achievement of unrealistic results is required. For example, getting maximum profit with minimum risk; construction in the shortest possible time with maximum quality. The solution of these problems (and as a consequence, the development of methods for solving problems of vector optimization) is carried out in several directions. We distinguish from these areas the main [6-8]: methods based on the collapse of the criteria (Weighted Sum Scalarization (WSS) Method), the method of the main criterion (satisfied requirements, 𝜀 −Constraint (EC) Method), the method of successive concessions, a group of methods of target programming (ideal point method, Weighted Chebyshev Scalarization (WCS) Method). The existence of such a large number of methods is a consequence of the "mathematical incorrectness" of the problem. Each of them has its disadvantages and advantages. Let's highlight the main ones. Methods that truncate the set of valid solutions Х can lead to sub-optimal Pareto solution (the main criterion method, method of successive concessions). Targeted programming methods (WCS) require the prior solution of single-criteria optimization problems for each partial criterion. The method of additive convolution (WSS) of criteria is considered to be one of the most popular [6, 8]. Its advantages are simplicity and the well-known fact that the resulting solution will be Pareto optimal [8]. It is necessary to obtain additional information from the DM on the weights of the performance criteria that characterize the degree of their importance. A known significant disadvantage is that this method is quite sensitive to small changes in the weights of the objective functions. Also, some iterative human- machine dialogic decision-making procedures are built on its basis [9]. An analysis of the existing relationships between the criteria will reduce the criteria space of tasks and provide important information for decision maker for a more sound selection of weights of performance criteria. 4. Clustering of criterion space Clustering is the process of dividing a given sample of objects (observations) into subsets (usually non-overlapping), called clusters, so that each cluster consists of similar objects, and the objects of different clusters differ significantly. One of the goals of clustering is to identify internal relationships between data by defining the cluster structure. Dividing observations into groups of similar objects simplifies further data processing. To group the efficiency criteria described by the objective functions 𝑓𝑖 (𝑥), 𝑖 = ̅̅̅̅̅̅ 1, 𝑚 use the following relationships between them. Definitions. We call two criteria strongly dependent on some set of admissible alternatives 𝑋, if the improvement of the score on one criterion on the set 𝑋 leads to its improvement by another criterion. Since the criteria are linear, the directions to the extreme coincide with the directions ±𝑔𝑟𝑎𝑑𝑓𝑖 (𝑥). If you move the beginning of the vector ±𝑔𝑟𝑎𝑑𝑓𝑖 (𝑥) with the beginning of the coordinate system, it coincides with the radius vector ̅̅̅̅̅ 𝑂𝐶𝑖 , where point 𝑂 – origin, 𝐶𝑖 (𝑐𝑖1 , 𝑐𝑖2 , … , 𝑐𝑖𝑛 ), 𝑖 = ̅̅̅̅̅̅ 1, 𝑚. Therefore, ̅̅̅̅̅ segmenting the vectors 𝑂𝐶𝑖 = 𝑐̅𝑖 into sets, thus segmenting the criteria that according to them 𝑓𝑖 (𝑥), 𝑖 = ̅̅̅̅̅̅ 1, 𝑚 . To implement the clustering process, a method based on fuzzy binary relations, item 6 in [10], was chosen. It allows you to group objects into clusters of different geometric shapes by changing only the types of similarity measures of objects (feature-vector of efficiency criteria). To determine the number of clusters, certain values are set - clustering thresholds 𝜇𝑅∗ , which characterize the degree of objects similarity in the inside of the cluster. The closer this value is to one, the more clusters are formed as a result. Conversely, a null value of 𝜇𝑅∗ will generate a single cluster that includes all objects. The similarity of objects by some criteria is characterized by a fuzzy binary relationship R on the set of vector features 𝐶 = {𝑐̅𝑖 |𝑖 = 1, ̅̅̅̅̅̅ 𝑚} with a membership function 𝜇𝑅 (𝑐̅𝑖 , 𝑐̅), 2 𝑗 where 𝜇𝑅 : 𝐶 → [0,1]. 𝜇𝑅 – characterizes the degree of similarity between objects with numbers 𝑖 and 𝑗 expressed in numerical value. It is obvious that the simultaneous improvement of the vectors of estimates of the partial efficiency criteria of problem (4) - (6) will occur when the directions, determining a feature vectors from С are close, ie the angle between them is small enough. Therefore, the degree of similarity for such clustering should be chosen based on the cosine of the angle between the feature vectors. Types of functions 𝜇𝑅 may be different. In particular, represented by formulas (7) and (8): 124 1 𝑐̅𝑖 ∙ 𝑐̅𝑗 (7) 𝜇1𝑅 (𝑐̅, ̅𝑗 ) = (1 + 𝑖 𝑐 ), 2 |𝑐̅𝑖 ||𝑐̅|𝑗 1 𝑐̅𝑖 ∙ 𝑐̅𝑗 (8) 𝜇𝑅2 (𝑐̅, 𝑖 𝑐̅𝑗 ) = 𝑎𝑟𝑐𝑐𝑜𝑠 ( ) + 1. 𝜋 |𝑐̅𝑖 ||𝑐̅| 𝑗 Function graphs 𝜇1𝑅 (dotted line) and 𝜇𝑅2 (solid line) is shown in Figure 1, where the abscissa axis determines the angle between the feature-vectors, and the ordinate axis - the value of the similarity measure. Figure 1: Graphs of similarity measures: 𝜇1𝑅 – dotted line, 𝜇𝑅2 - solid line Each of the functions determines the similarity measures of feature-vectors by the angle between them: the smaller the angle, the value of functions (7), (8) will approach 1; the closer the angle is to 180°, the closer the value of the similarity measures will be to zero. Graphs of similarity measure 𝜇1𝑅 very slowly descends around the point 𝑥 = 0, therefore accurately determine the clustering threshold 𝜇𝑅∗ will be quite difficult when using this feature. Therefore, it is expedient to use a similarity measure (8) when using a clustering method based on fuzzy binary relations. We describe a modification of the crisp method of single-level clustering item 6 in [10] to use the angular similarity measure (8). Let Ω1 ={1, 2, …, m}. Next, the l-th iteration is described step by step. Step 1. We choose the dominant centroid vector с̅𝑙∗ from the set {𝑐̅𝑖 |𝑖𝜖Ω𝑙 }, around which the l-th cluster will be built. This vector can be arbitrary or determined by a specific rule. In particular, given the heuristics, it is recommended to assign as dominant one of the vectors {𝑐̅𝑖 |𝑖𝜖Ω𝑙 }, which provides the maximum value of the function R in relation to all other vectors from {𝑐̅𝑖 |𝑖𝜖Ω𝑙 }. All {𝑐̅𝑖 |𝑖𝜖Ω𝑙 }, for which 𝜇𝑅2 (𝑐̅, ̅∗ ∗ 𝑙 𝑖 𝑐𝑙 ) ≥ 𝜇𝑅 , is valid are included in the conventional cluster 𝑈 . 𝑙 Step 2. The procedure of alignment of the cluster 𝑈 is performed. For this, the centroid vector is recalculated. For the two-dimensional clustering problem, the notion of a centroid is close to the notion of the bisector of the largest angle between the vectors of gradients of efficiency criteria inside one cluster 𝑈 𝑙 . Therefore, in this case, the centroid can be determined by the formula: 𝑐̅𝑙∗ = (𝑐̅̅̅ 𝑖∗ + ̅̅̅)/2, 𝑐𝑗∗ (9) 𝑐̅𝑖∙𝑐̅𝑗 where {𝑖 ∗ , 𝑗 ∗ }𝜖𝑎𝑟𝑔 min𝑙 (|𝑐̅ ||𝑐̅ |) and 𝐼𝑙 = {𝑖|𝑐̅𝜖𝑈 𝑖 𝑙 }. 𝑖,𝑗∈𝐼 𝑖 𝑗 That is, the centroid is co-directed with the bisector of the largest angle between any feature vectors belonging to the cluster 𝑈 𝑙 . For larger problems, it is proposed to calculate the centroid vector as the center of gravity of the points corresponding to the ortho-vectors of the gradients within one cluster 𝑈 𝑙 : 125 1 𝑐̅𝑖 (10) 𝑐̅𝑙∗ = 𝑙 ∙ ∑ . ‖𝑈 ‖ |𝑐̅𝑖 | 𝑙 𝑐̅𝑖𝜖𝑈 Items with 𝑈 𝑙 : 𝑈 𝑙 =Ø are cleared. Further, a new refined cluster is formed 𝑈 𝑙 = {𝑐̅𝜖Ω 𝑖 2 𝑙 |𝜇𝑅 (𝑐 ̅∗ ∗ 𝑖 𝑐𝑙 ) ≥ 𝜇𝑅 }. ̅, The procedure of alignment of the cluster 𝑈 𝑙 is held until the 𝑐̅𝑙∗ coordinates change in recalculation. Otherwise, we proceed to the next step. Step 3. The procedure of refinement of the cluster 𝑈 𝑙 is performed. For this, the vector 𝑐̅𝑝 , which is “the most similar” to the vector 𝑐̅𝑙∗ , is determined from the set Ω𝑙 /𝑈 𝑙, i.e., 𝜇𝑅2 (𝑐̅𝑝 , 𝑐̅𝑙∗ ) = = max 𝜇𝑅2 (𝑐̅, ̅∗ 𝑖 𝑐𝑙 ). 𝑖𝜖Ω𝑙 /𝑈 𝑙 And the possibility of joining 𝑐̅𝑝 to 𝑈 𝑙 is checked. For the set 𝑈 𝑙 ∪ {𝑐̅𝑝 }, the centroid vector ̅̅̅̅ 𝑐𝑙∗∗ is calculated according to the formulas (9) or (10). If the set {𝑐̅𝜖𝑈 𝑖 𝑙 ∪ {𝑐̅𝑝 }|𝜇𝑅2 (𝑐̅, ̅̅̅̅ ∗∗ ∗ 𝑙 𝑖 𝑐𝑙 ) ≥ 𝜇𝑅 } is equal to the set 𝑈 ∪ {𝑐̅𝑝 }, the vector 𝑐̅𝑝 is included in the set 𝑈 𝑙 , and the centroid vector 𝑐̅𝑙∗ is recalculated, i.e. 𝑐̅𝑙∗ = ̅̅̅̅ 𝑐𝑙∗∗ . If {𝑐̅𝜖𝑈 𝑖 𝑙 ∪ {𝑐̅𝑝 }|𝜇𝑅2 (𝑐̅, ̅̅̅̅ ∗∗ ∗ 𝑖 𝑐𝑙 ) ≥ 𝜇𝑅 } ≠ 𝑈 𝑙 ∪ {𝑐̅𝑝 }, the procedure of refinement of the cluster 𝑈 𝑙 is completed. Step 4. We form the cluster 𝐾 𝑙 =𝑈 𝑙 and Ω𝑙+1 =Ω𝑙 /𝐾 𝑙 . If Ω𝑙+1 ≠ ∅, we proceed to step 1. Otherwise, the clustering procedure is completed. The result of the method will be crisp clusters 𝐾1 , 𝐾2 , … , 𝐾𝑧 , 𝑧 ≤ 𝑚 with appropriate centroids ̅∗ ̅∗ 𝑐1 , 𝑐2 , … , 𝑐̅𝑧∗ is performed. Thus, the criterion space of problem (4) can be reduced by the space of centroids 𝑐̅1∗ , 𝑐̅2∗ , … , 𝑐̅𝑧∗. If you need information not only about the distribution of efficiency criteria by clusters, but also about the degree of belonging to each of them, it is necessary to carry out the procedure of fassification of item 8 in [10]. 5. Reducing space of criteria in the weighted sum scalarization method 5.1. Weighted sum scalarization method In the study of MOP, it seems obvious that a solution can be obtained using the additivity of the vector criterion. Indeed, the need to make a decision taking into account all particular criteria leads to the quite obvious conclusion that each particular criterion makes its own "contribution" to the final assessment of one or another alternative. To obtain such an estimate in an explicit form, it is required to construct a functional that is intended to serve as the final (resulting, integral) criterion. Pareto drew attention to this and introduced the concept of weights. The vector of weight coefficients of criteria is set 𝛼 = (𝛼𝑖 , 𝑖 = ̅̅̅̅̅̅ 1, 𝑚 ), which characterizes the relative importance of the relevant criterion for it. Approaches to determining weights are described in [11-13]. Weights are usually used in normalized form and satisfy the conditions ∑𝑚 𝑖=1 𝛼𝑖 = 1, 𝛼𝑖 ≥ ̅̅̅̅̅̅ 0, ∀𝑖. If we find the sum of the criteria 𝑓𝑖 (𝑥), 𝑖 = 1, 𝑚, multiplied by their weights, we obtain a linear scalarized function that is maximized on the allowable range of constraints 𝑋. The one-criteria (scalar) problem of mathematical programming is received: 𝑚 (11) 𝐹∗ = ∑ 𝛼𝑖 𝑓𝑖 (𝑥 ) → 𝑚𝑎𝑥 𝑖=1 (12) 𝑔𝑘 (𝑥 ) ≤ 𝑏𝑘 , 𝑘 = ̅̅̅̅̅ 1, 𝑝, 𝑥𝑗 ≥ 0, 𝑗 = ̅̅̅̅̅ 1, 𝑛 𝑚 (13) ∑ 𝛼𝑖 = 1, 𝛼𝑖 ≥ 0. 𝑖=1 In most cases, the construction of the convolution is preceded by the execution of the normalization of particular criteria. The essence and meaning of this operation is to get rid of differences in dimension that may occur for individual particular criteria, as well as to reduce the sets of their possible values to 126 the same fixed numerical segment (as a rule, segment [0; 1]). This makes it possible, in particular, to exclude situations when the transition, say, from estimates in one measurement unit to another can affect the final decision made by the DM. As a result of solving the problem (11) - (13), we obtain the point of the optimum 𝑥 ∗ ∈ 𝑋, which satisfies condition (3). Despite the fact that the point obtained as a result of solving problem (11) - (13) 𝑥 ∗ ∈ 𝑋 is Pareto optimal, additive convolution of criteria has a number of disadvantages. Therefore, the selection 𝛼𝑖 must be justified. Often the resulting solution is unstable, i.e., small increments of weights correspond to large increments of objective functions. 5.2. Reducing the dimensionality of the criteria space and determination of weights in the WSS method Suppose a vector problem of linear programming is given, the criterion space of which contains three criteria on a set of alternatives Х (Figure 2). According to the WSS method, the decision maker needs to determine the weights that match the priority criteria. Figure 2: Geometric interpretation of the multipurpose linear optimization problem In Figures 2 and 3, the bold line highlights the set of Pareto AB non-improving alternatives and local solutions of the problem. As can be seen, the local optimum points for the first and second criteria coincide and are at point A, i.e., it is obvious that the improvement of the evaluation vector for one of them leads to the automatic improvement of the evaluation for the other. Therefore, it becomes obvious that this fact must be taken into account when determining the weights of the decision maker. Of course, in problems of higher dimension it is very difficult (or impossible) to make a geometric interpretation, so the clustering of the criterion space by the angular similarity measure at the value of the thresholds 𝜇𝑅∗ close to the unit just and will allow you to identify highly dependent criteria. Consider its application in this example (Figure 3). Figure 3 shows that after clustering, the objective functions 𝑓1 and 𝑓2 will represent the centroid of the cluster 𝑓 ∗ = 𝑎(𝑓1 + 𝑓2 ), which is the collinear sum of the first two vectors. To reduce the criterion space, in the future, we can not consider all the vectors, but only the centroids of the clusters. That is, in the context of the example, the output was a two-criterion problem with objective functions 𝑓 ∗ and 𝑓3 . Further, the decision maker can assign weights according to different approaches, ranking not all partial criteria, but formed clusters of criteria. 127 Figure 3: Geometric interpretation of the result of clustering of criterion space by angular similarity measure In particular, the following approaches can be used.  If all criteria are equivalent or the DM finds it difficult to rank them, then more weight can be given to those centroids that represent a more powerful cluster: |𝐾𝑖 | (14) 𝛽𝑖 = , 𝑚 where 𝛽𝑖 – weighting factor of the i-th centroid, |𝐾𝑖 |- the number of elements of the i-th cluster, m- the total number of efficiency criteria in the problem.  If the decision maker can compare clusters of criteria in pairs, then a square matrix of pairwise comparisons is created 𝐵 dimension 𝑧 × 𝑧, elements 𝑏𝑖𝑗 which can take binary values: 1, if the criteria of the cluster 𝐾𝑖 prevail over the group of criteria of the cluster 𝐾𝑗 ; 0 – otherwise. ∑𝑧𝑗=1 𝑏𝑖𝑗 (15) 𝛽𝑖 = , ∑𝑧𝑖,𝑗 𝑏𝑖𝑗 In essence, this approach uses only simple linear convolutions (WSS method) with different weights, which are not selected arbitrarily, but on the basis of information about the relationship between the criteria. Therefore, in this example, the use of the clustering approach has only slightly modified the method of simple linear convolution and this ensures that the solution found will be Pareto optimal (non-improving, efficient). 5.3. General scheme of criterion space reduction for the WSS method Here is a general scheme of using the approach of clustering the criterion space of a multipurpose linear programming problem (Figure 4). Thus, the use of the method based on fuzzy binary relations and similarity measure (8) allows to structure the criterion space of the problem into clusters of strongly dependent criteria. The result of grouping is not only clusters 𝐾1 , 𝐾2 , … , 𝐾𝑧 , and their centroids 𝑓1∗ , 𝑓2∗ , … , 𝑓𝑧∗ , 𝑧 ≤ 𝑚, which will be the new objective functions of the reduced criterion space. It should be emphasized that the obtained centroids are already normalized. Next, the decision maker assigns weights 𝛽1 , 𝛽2 , … , 𝛽𝑧 , which are used in a simple linear convolution of the criteria of reduced space: 𝑧 ∗ (16) 𝐹=∑ 𝛽𝑖 ∙ 𝑓𝑖 . 𝑖=1 128 Figure 4: Scheme of reduction of criterion space of MOP at use WSS method At the output we get a single-criteria problem. Methods for solving single-criteria problems of linear programming are presented in detail in [14-16]. The solution of this problem 𝑥 ∗ will be Pareto optimal and non-improving. Next, you need to find the vector of evaluations (𝑓1 (𝑥 ∗ ), 𝑓2 (𝑥 ∗ ), … , 𝑓𝑚 (𝑥 ∗ )) that are provided to the decision maker for analysis. If the obtained values of the efficiency criteria satisfy the decision-maker, then the process of finding a solution is considered complete. If not, the DM should increase the weights of the groups of criteria whose values need to be improved. The numerical ratios of the weights of all other criteria must be left unchanged. Thus, it is possible to develop a dialog human-machine procedure for finding solutions to multicriteria linear programming problems. 6. Conclusions This work is a continuation of research [10, 17] on the use of the clustering method based on fuzzy binary relations [10] in solving different classes of applied problems. It is devoted to the urgent problem of increasing the efficiency of methods for solving multi-objective problems of linear programming by applying the approach of clustering the criterion space, identifying strongly dependent efficiency criteria, further reduction of the criterion space of the problem into a smaller centroid space. This allows you to structure the criteria space and provide additional information about the relationships between the criteria to the decision maker for a more accurate selection of weights. The analysis of the current state of research of multipurpose optimization problems is carried out. The clustering method based on fuzzy binary relations was adapted [10] to detect groups of vectors similar in angular similarity measure (8). The approach of reduction of the criterion space of the problem by the space of centroids is described. In this case, the centroids are already normalized. Based on this approach, the Weighted sum scalarization method in the selection of a decision maker the weights of the efficiency criteria has been modified. The scheme of the complex approach to the decision of multi-objective problems of linear programming with use of the approach of criterion space reduction is presented. In future research, we plan to use the proposed approach in developing a decision support system for some applications. In particular, for the calculation of individualized diets for a nutritionist. They may contain equivalent criteria for the decision-maker, so they need to structure the criteria space. 7. Acknowledgements The work is supported by the state budget scientific research project of Uzhgorod National University “Methods of computational intelligence for data processing and analysis” (state registration number 0121U109279). 129 8. References [1] Vanderbei, Robert J. Linear programming. Vol. 3. Heidelberg: Springer, 2015. [2] Federica Monaco, et al. "Water management options for rice cultivation in a temperate area: a multi-objective model to explore economic and water saving results." Water 8.8 (2016): 336. https://doi.org/10.3390/w8080336. [3] Habibi Davijani,et al. "Multi-objective optimization model for the allocation of water resources in arid regions based on the maximization of socio-economic efficiency." Water resources management 30.3 (2016): 927-946. https://doi.org/10.1007/s11269-015-1200-y. [4] Zhang Weili, Charles Nicholson. "A multi-objective optimization model for retrofit strategies to mitigate direct economic loss and population dislocation." Sustainable and Resilient Infrastructure 1.3-4 (2016): 123-136. https://doi.org/10.1080 / 23789689.2016.1254995. [5] Nurjanni, Kartina Puji, Maria S. Carvalho, and Lino Costa. "Green supply chain design: A mathematical modeling approach based on a multi-objective optimization model." International Journal of Production Economics 183 (2017): 421-432. https://doi.org/10.1016/j.ijpe.2016.08.028. [6] Gunantara Nyoman. "A review of multi-objective optimization: Methods and its applications." Cogent Engineering 5.1 (2018): 1-16. https://doi.org/10.1080/23311916.2018.1502242. [7] Podviezko Askoldas, Valentinas Podvezko. "Influence of data transformation on multicriteria evaluation result." Procedia Engineering 122 (2015): 151-157. https://doi.org/10.1016/j.proeng.2015.10.019. [8] Kasimbeyli, Refail, et al. "Comparison of some scalarization methods in multiobjective optimization." Bulletin of the Malaysian Mathematical Sciences Society 42.5 (2019): 1875-1905. https://doi.org/10.1007 / s40840-017-0579-4. [9] Ghaznavi, Mehrdad, Mohammad Ilati, and Esmaile Khorram. "An interactive algorithm for solving multiobjective optimization problems based on a general scalarization technique."Iranian journal of numerical analysis and optimization 6.1 (2016): 79-101. https://doi.org/10.22067 / IJNAO.V6I1.44631. [10] Natalia Kondruk, “Clustering method based on fuzzy binary relation.” Eastern-Europ. J. of Enterprise Technologies, 2.4 (86) (2017): 10–16. https://doi.org/10.15587/1729- 4061.2017.94961. [11] Odu, G. O. "Weighting methods for multi-criteria decision making technique." Journal of Applied Sciences and Environmental Management 23.8 (2019): 1449-1457. https://doi.org/10.4314 / jasem.v23i8.7. [12] Rezaei, Jafar. "Best-worst multi-criteria decision-making method: Some properties and a linear model." Omega 64 (2016): 126-130. https://doi.org/ 10.5267 / j.dsl.2018.3.003. [13] Pamučar, Dragan, Željko Stević, and Siniša Sremac. "A new model for determining weight coefficients of criteria in mcdm models: Full consistency method (fucom)."Symmetry 10.9 (2018): 393. https://doi.org/10.3390/sym10090393. [14] Goldman, A. J., Tucker, A. W. "4. Theory of Linear Programming". Linear Inequalities and Related Systems. (AM-38) 38 (2016): 53-98. https://doi.org/10.1515/9781400881987-005. [15] Dyer, Martin, et al. "Linear programming." (2017): 1291-1309. https://doi.org/10.1201/9781315119601. [16] Mansini, Renata, Wlodzimierz Ogryczak, and M. Grazia Speranza. "Twenty years of linear programming based portfolio optimization." European Journal of Operational Research 234.2 (2014): 518-535. https://doi.org/10.1016/j.ejor.2013.08.035. [17] Natalia Kondruk, Mikola Malyar. "Analysis of Cluster Structures by Different Similarity Measures."Cybern Syst Anal 57 (2021): 436–441. https://doi.org/10.1007/s10559-021-00368-4. 130