=Paper=
{{Paper
|id=Vol-3018/Paper_11.pdf
|storemode=property
|title=Dimensionality Reduction of the Criterion Space in Some Optimization Problems
|pdfUrl=https://ceur-ws.org/Vol-3018/Paper_11.pdf
|volume=Vol-3018
|authors=Natalia Kondruk,Mykola Malyar
|dblpUrl=https://dblp.org/rec/conf/intsol/KondrukM21
}}
==Dimensionality Reduction of the Criterion Space in Some Optimization Problems==
https://ceur-ws.org/Vol-3018/Paper_11.pdf
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