of the Feasible Set in Criterion Space in Nonlinear MCDA Problems
by
A. Lotov, G. Kamenev, and V. Berezkin
Russian Academy of Sciences, Computing Center,
Department for Economic Decision Analysis
Vavilova, 40, Moscow 117967, Russia
Visualization of information, i.e. transformation of symbolic data into geometric information that aids in forming a mental picture of the data, turned out to be the most effective tool of human-computer communication. Multiple Criteria Decision Aid (MCDA) procedures can benefit from applying visualization. Our approach introduced in [1] is based on visualization of the Feasible Set in Criterion Space (FSCS). User (decision maker or expert) obtains general orientation in the criterion space that may help him to access the limits of what is possible in terms of criteria. In the case of more than two criteria, visualization is based on approximating the FSCS by simple figures and subsequent on-line display of the approximation using its two-criterion slices. Visualization of the FSCS can be incorporated into various MCDA methods. Say, it can be used for visualization of location of the current solution in interactive MCDA procedures. However, its most effective real-life application turned out to be related to goal programming, in the framework of which visualization of the FSCS helps to identify a preferable feasible goal (Feasible Goals Method, the FGM).
In the linear case, the FSCS is convex. For this reason, a polyhedral approximation of it can be constructed using a combination of optimization and Fourier convolution of linear inequalities ([2], [3]). If the number of criteria does not exceed seven, the approximation can be as precise as desired. Due to this, the Pareto set in criterion space can be displayed as the frontier of the FSCS; user can obtain information on efficient criterion tradeoff. Collections of two-criterion slices of the approximation can be even animated. These features help to apply the FGM in real-life decision problems described by large linear models (see [2] and [3]).
The problem is much more complicated in the nonlinear case, for which the FSCS is usually non-convex. In this case, as it was proposed in [4], collections of boxes (parallelotops) with edges that are parallel to the coordinate axes are used for approximating the FSCS. Centers of the boxes are computed as filtered outputs of random feasible decision points.
Assume that the decision set X belongs to a metric space W and the criterion space is R^{m} with the Tchebycheff metrics. Let us consider a mapping f from W to R^{m}. Then, the FSCS is Y = f(X). Let m be the uniform measure defined on X, m (X) = 1. We assume that X is the unification of a finite number of compact measurable sets, on which f is continuos. Let us consider a finite collection T of points from Y (covering base) and the set (T)e , the e -neighborhood of T, which is the approximating set of boxes. The quality of the approximation is measured by the values of e and
h(e) = (m(f^{ -1}((T)e_{Ç}Y)),
which shows what portion of X results in criterion points that belong to (T)e . The following iterative method is used for constructing a covering base T that results in a desired (e*, h *)-approximation of Y with given 0 < h* < 1 and 0 < e*. Before any iteration, a covering base T is supposed to be given. Iteration consists of three steps:
The approximation is visualized in the form of collections of two-criterion slices, which can be computed and displayed fairly fast. In a picture, the values of two criteria are given on axes, values of a third criterion are associated with colors, which change from slice to slice, and the ranges of all other criteria are specified (see Figure). User can explore a large number of pictures of this kind displayed on-line.
User may want to identify a preferable feasible goal on display. Then, a point from T that contains the identified goal in its e -neighborhood and the associated decision are found. Since the FSCS is approximated roughly, additional techniques for fine-tuning the feasible goal may be helpful.
The software that implements the above method was coded in the form of the add-in tool for MS Excel. It consists of four subsystems. The first one helps to formulate a nonlinear model using MS Excel means. The second one helps to specify criteria and approximation parameters. The covering base is constructed in the form of a table in the third subsystem. The last one visualizes the approximation on-line and helps to select a preferable goal on display. The software is described in [5]. A demo version can be found in Web at http://www.ccas.ru/mmes/mmeda.
The method requires large number of simulation runs. So,
it can be applied in the case of relatively simple models (say, in early
decision screening). However, the scope of its application can be broadened
by its implementation at parallel and meta-computing platforms. Important
that the method is ready for such implementation.
References
[1] Lotov, A.V. (1973), "An approach to perspective planning in the case of absence of a single objective", Proceedings of Conference on Systems Approach and Perspective Planning (Moscow, May 1972), Computing Centre of USSR Academy of Sciences, Moscow, 205-208 (in Russian).
[2] Lotov, A., Bushenkov, V., and Kamenev, G. (1999), Feasible Goals Method. Mathematical Foundations and Environmental Applications, Edwin Mellen Press, Lewiston, NY USA, 400 p. (in Russian).
[3] Lotov, A., Bushenkov, V., and Kamenev, G. (2001), Feasible Goals Method. Search for Smart Decisions, Computing Centre RAS, Moscow, Russia, 240 p. (in English).
[4] Kamenev, G., and Konratíev, D. (1992), "Method for Exploration of Non-Closed Nonlinear Models", Matematicheskoe Modelirovanie (Mathematical Modelling) 4(3), 105-118 (in Russian).
[5] Berezkin, V.E., Kamenev, G.K., and Lotov, A.V. (2000),
Implementation of Feasible Goals Method for Nonlinear Case in MS Excel
Environment, Computing Centre RAS, Moscow, Russia, 42 p. (in
Russian).
Figure. Black and white copy of color display. Collection
of slices for five criteria problem is given. Two criteria (f4 and
f5) are located on axes. Intervals of the value of f1 are
given by shading here (color on display). Ranges of f2 and f3
were specified.