Software for Visualization

of the Feasible Set in Criterion Space in Nonlinear MCDA Problems


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 Rm with the Tchebycheff metrics. Let us consider a mapping f from W to Rm. 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:

  1. outputs of N random independent points from X are computed;
  2. these outputs are used for estimating the dependence h(e) for the covering base T and testing the termination condition h(e*)? h* with a reliability ? < 1 that depends on h* and N;
  3. if the termination condition is not satisfied, T is augmented by one or several output vectors that are most distant from T.
The number of points in the covering base T that solves the problem depends on the form of the set f(Y). For this reason, user may want to interrupt the process and select a satisficing value of e . To support such decision, the dependence h(e) is displayed after any iteration. Detailed description of the method is given in [3].

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

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.


[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.