Algorithmic aspects to analysis of decision maker's preferences structure with standard aggregative functions

There are two non-trivial tasks in the considered in the previous paper algorithm of checking if some object is optimal. First task is about potential ability for an object to be optimal. It solves by checking if an object belongs to conv_P(Y) - Pareto-envelope of Y set, obtained as a union of 2ⁿ Pareto-sets Y_P for all combinations of directions for n criteria. Second task is about to determine the type of aggregative function and weight vector which make an object optimal. It contains the checking if an object belongs convL(Y) - linear convex envelope Y. Here Y is a set of vectors which characterizes the set of objectsX: y(x) = f1(x),f₂(x), ..., f_n(x)), x e X, y(x) e Y. Any vector is a point in n-dimensional space Rⁿ, and envelopes convP(Y) and convL(Y) are the general form polytope and the convex polytope, framing Y. Both of polytopes contains at least all points y_ex having extreme value of at least one of coordinates: y_ex e conv_L(Y) n conv_P(Y) < 3J = 1, n:(f(x) = max _xeX (f(x)) vf(x) = min _xeX (f(x))). And also conv_L(Y) с conv_P(Y). We declare then the Pareto envelope cannot be found with an algorithm less complex then reduced search: 1. Calculating the Pareto set for any of 2ⁿ combinations of directions of n criteria using the pairwise comparisons. The computational complexity of calculating the Pareto set is n • N • (N-1)/2 ~ n • N² at worse case, N = | Y |. That worse case is if all objects are Pareto incomparable. In that case, all N objects will be in Pareto set YP. However, in general, there is a possibility of reducing the calculating: if one object is dominated by another, we must exclude that dominated object from the further search. Therefore, in the best case the computational complexity will be n • (N-1) ~ n • N. In this case, we have one best object, which we will compare with others. We recommend to start with objects from the set {y_ex} in order to provide the maximal reducing. 2. Unioning of Y_P. Computational complexity (N-1) • n ~ n • N is less then above and it can be neglected. So approximately computational complexity of conv_P(Y) construction algorithm is 2ⁿ • n • N² at worse case and 2ⁿ • n • N at best case. For linear convex envelope conv_L(Y) construction in two-dimension space we can use the Graham scan and its modifications, but with quantity of dimensions n>2 it is not applicable. Instead of Graham scan we consider the following reducing search algorithm using the fact that conv_L(Y) с conv_P(Y). 1. For all of 2ⁿ combination of directionsf(x) ^ {min, max}, J = 1, ., n: a. Choose one object from conv_P(Y), having extreme value at least of one criteria and construct the hyperplane L passing through them. The complexity is n • (N + n²) ~ n³. The cubical component is from need to calculate the determinant for hyperplane construction. b. Choose or form the new "limited" point y_extr, having extreme values of all fj(x) with given combination of directions and calculate the oriented distance d between it and the hyperplane. The complexity is n • (N + 1) ~ N• n. c. Form the Y*c conv_P(Y) from objects for which the oriented distance to hyperplane has the same sign that d, another neglected. The complexity is N • n. d. The set Y_t с Y forming by iterative repeating a-c for all sets of n points from Y . If | Y | < n + 1, then Y_t = Y . The complexity at the worse case is C_N • (n³+N • n), and at the best - 0. 2. The envelope convL(Y) is union of all Yt. The complexity is less then above and can be neglected. So approximately computational complexity of conv_L(Y) constructing algorithm is 2ⁿ • C_N • n •(n² + N) at the worse case and 2ⁿ • n • (n²+N) at the best.

Keywords

Authors

References