- Email: [email protected]

Decision Aiding

Synchronous approach in interactive multiobjective optimization Kaisa Miettinen b

a,*

, Marko M. Ma¨kela¨

b

a Helsinki School of Economics, P.O. Box 1210, FIN-00101 Helsinki, Finland Department of Mathematical Information Technology, P.O. Box 35 (Agora), FIN-40014, University of Jyva¨skyla¨, Finland

Received 9 September 2003; accepted 1 July 2004 Available online 18 September 2004

Abstract We introduce a new approach in the methodology development for interactive multiobjective optimization. The presentation is given in the context of the interactive NIMBUS method, where the solution process is based on the classiﬁcation of objective functions. The idea is to formulate several scalarizing functions, all using the same preference information of the decision maker. Thus, opposed to ﬁxing one scalarizing function (as is done in most methods), we utilize several scalarizing functions in a synchronous way. This means that we as method developers do not make the choice between diﬀerent scalarizing functions but calculate the results of diﬀerent scalarizing functions and leave the ﬁnal decision to the expert, the decision maker. Simultaneously, (s)he obtains a better view of the solutions corresponding to her/his preferences expressed once during each iteration. In this paper, we describe a synchronous variant of the NIMBUS method. In addition, we introduce a new version of its implementation WWW-NIMBUS operating on the Internet. WWW-NIMBUS is a software system capable of solving even computationally demanding nonlinear problems. The new version of WWW-NIMBUS can handle versatile types of multiobjective optimization problems and includes new desirable features increasing its user-friendliness. 2004 Elsevier B.V. All rights reserved. Keywords: Multiple objective programming; MCDM; Internet; Interactive methods; NIMBUS; WWW-NIMBUS; Nonlinear programming

1. Introduction

* Corresponding author. Tel.: +358 14 260 2743; fax: +358 14 260 2731. E-mail addresses: [email protected]ﬁ (K. Miettinen), [email protected]ﬁ (M.M. Ma¨kela¨).

Many real-life optimization problems have several conﬂicting objective functions that should be minimized or maximized simultaneously. In such multiobjective optimization problems, ﬁnding the best possible solution means trading oﬀ between

0377-2217/$ - see front matter 2004 Elsevier B.V. All rights reserved. doi:10.1016/j.ejor.2004.07.052

910

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

the diﬀerent objectives. Instead of a single optimal solution, we have a set of compromise solutions, so-called Pareto optimal solutions where none of the objective function values can be improved without impairing at least one of the others. To be able to identify the best Pareto optimal solution, we need some additional information in the form of preferences from a decision maker, a person who has expertise on the problem domain. Scalarizing functions play an important role in multiobjective optimization methods [15]. Via scalarization, the multiple objectives together with some preference information from the decision maker are transformed into a single objective function, which can be optimized with conventional methods [1]. The decision maker can specify preference information a priori (after which a solution satisfying this information as well as possible is found) or a posteriori (after a representation of the Pareto optimal set has been generated). Alternatively, the decision maker may take actively part in the solution process and specify preference information interactively. The advantages of the latter approach include that the decision maker can learn about the problem and the interrelationships between the objectives, and adjust her/his hopes on a realistic level. Besides, computational costs (when compared to a posteriori methods) are much smaller because only solutions that are of interest to the decision maker are generated. Assuming the decision maker has time enough for taking part in an interactive solution process, the ﬁnal solution is expected to be more satisfactory than with the other approaches because the decision maker has a possibility to aﬀect and direct the solution process to a desired direction and possibly even change her/his mind while learning. For further information about diﬀerent method types, see, for example [11,15]. In what follows, we concentrate on interactive multiobjective optimization methods. In general, they diﬀer from each other in terms of scalarization functions and preference information used [5,11,15]. Widely-used ways for the decision maker to express her/his preferences are to use reference points or to classify the objective functions. A reference point consists of desirable values for each objective function whereas the classiﬁcation indi-

cates what kind of changes are desirable in the objective function values. Descriptions of methods utilizing reference points can be found, for example, in [3,12,15,27] and methods based on classiﬁcation in [2,15,16,26], among others. Since reference points and classiﬁcation are closely related, they can even be used in the same context. As an example we can mention the satisﬁcing trade-oﬀ method [23], where reference points are formed based on classiﬁcation and some additional information. Normally, one scalarizing function is used in each method and the selection of this function is up to the method developer. However, it has been shown that diﬀerent scalarizing functions may lead to even clearly diﬀerent solutions even though they are based on exactly the same preference information [4,19]. Thus, one can say that by ﬁxing the scalarizing function the method developer also ﬁxes the solution obtained. This is not desirable because there is no general way how to identify the best of the diﬀerent solutions without involving the decision maker. The diﬃculty here is exactly the same as with Pareto optimal solutions in general: which one is the best solution to be selected as the ﬁnal one. Ideas have been suggested in the literature to connect several multiobjective optimization methods in order to use them sequentially (see, for example, [10]). This means that diﬀerent scalarizing functions and diﬀerent ways of expressing preference information are used. Even though this kind of a uniﬁed approach brings versatility into the solution process, it requires the active involvement of the decision maker when changing the method. In other words, the decision maker must know the functioning and the prerequisites of the methods available. Usually, interactive methods that generate a set of diﬀerent Pareto optimal solutions for the decision maker to compare are based on altering the preference information in one way or the other. As examples, we can mention the reference point method [27] and the reference ball method [28], where the reference point is shifted. For more examples, see [15] and references therein. In this paper, we introduce a new approach of synchronously using several, both classiﬁcation

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

and reference point based, scalarizing functions based on the same preference information of the decision maker. What we here mean by a synchronous approach is related to the fact that we use several scalarizing functions (based on the same preference information) in order to get several Pareto optimal solutions. This new idea diﬀers from the earlier approaches in the respect that preference information is not artiﬁcially altered or parametrized in order to produce diﬀerent solutions (like, for example, in [5,12,25–27]). With the synchronous approach, the decision maker may obtain several solutions, each theoretically reﬂecting the preferences equally well but still giving an impression of the variety of diﬀerent solutions. The advantage of this approach is the fact that it is the decision maker and not the method developer who judges which solution is the most satisfactory one. Simultaneously, a better view of the potential solutions is provided based on the preference input once expressed. On the other hand, giving more information to the decision maker does not necessitate asking any more preference information from her/him. Furthermore, the diﬀerent scalarizing functions may treat the same preference information either in a strict or a more suggestive way allowing the decision maker to compare the consequences. We apply the synchronous approach and describe a synchronous variant of the NIMBUS method. NIMBUS is a Nondiﬀerentiable Interactive Multiobjective BUndle-based optimization System (see [15,17]). During the interactive solution process, the user of NIMBUS can evaluate the problem to be solved as well as oneÕs preferences in a ﬂexible way. NIMBUS is based on the classiﬁcation of the objective functions into up to ﬁve classes according to the desires of the decision maker at the current solution. In the ﬁrst variant of NIMBUS, this information was transformed into a multiobjective optimization subproblem [16], whereas in the second variant, the classiﬁcation information was scalarized [15,17]. As far as these two variants are concerned, their comparison is given in [17] and both of them have been used in solving several real-life problems. Among others, they have been applied in a structural design problem [20], in the optimal control problem of the

911

continuous casting of steel [21] and in the paper machine headbox design [9]. Results with both small-scale and large-scale problems give evidence about the reliability and eﬃciency of the method. Besides the new synchronous aspects of the NIMBUS method, we introduce a new scalarizing function. In other words, we replace the scalarizing function used in the second variant of NIMBUS by a new one. We introduce this new function because of its computational eﬃciency when compared to the earlier approaches. The NIMBUS method is general in nature and can be applied for solving both linear and nonlinear problems involving both continuous and integer-valued variables. What is essential is the single objective optimizer needed for solving the scalarized problems the method produces. In general, it is diﬃcult to ﬁnd software for continuous (nonlinear) multiobjective optimization problems. To ﬁll this evident gap in the ﬁeld of optimization software the NIMBUS method has been implemented as a WWW-NIMBUS software system operating on the Internet [18]. It is easily accessible at http://nimbus.mit.jyu.ﬁ/ and freely available for academic research purposes. WWW-NIMBUS is based on the ideas of centralized computing and distributed interface. With software operating on the Internet, no special requirements are set on the userÕs computer. This means that the operating system used or the compilers available play no role. In other words, no software has to be downloaded and it is always the latest version that is used. Furthermore, a convenient and graphical user interface can be implemented with visualization possibilities. The version 1.0 of WWW-NIMBUS was the ﬁrst World-Wide Web (WWW) based interactive optimization software as early as in 1995. In what follows, we describe the implementation of the synchronous NIMBUS algorithm as the version 4.0 of the WWW-NIMBUS system. This software contains four diﬀerent scalarizing functions based on the classiﬁcation information once expressed by the decision maker. The choice of these particular scalarizing functions is based on the numerical and theoretical comparisons presented in [19]. The ﬂexibility of WWW-NIMBUS is increased by a convenient database management facility and the

912

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

possibility to select the single objective optimizer to be used. Furthermore, the variety of diﬀerent problem types that the system can handle has been extended. The rest of this paper is organized as follows. We introduce the basic concepts in Section 2 whereas Section 3 is devoted to the scalarizing functions and the related subproblems to be used. In Section 4, we describe the new synchronous NIMBUS algorithm, and WWW-NIMBUS, its implementation on the Internet is the topic of Section 5. We give a short numerical example in Section 6 and conclude the paper in Section 7.

2. Concepts We handle multiobjective optimization problems of the form minimize

ff1 ðxÞ; f2 ðxÞ; . . . ; fk ðxÞg

subject to

x2S

ð2:1Þ

involving k (P2) conﬂicting lower semicontinuous objective functions fi: Rn!R that we want to minimize simultaneously. The decision (variable) vectors x = (x1, x2, . . . , xn)T belong to the nonempty compact feasible region S Rn. Objective vectors consist of objective (function) values f(x) = (f1(x), f2(x), . . . , fk(x))T and the image of the feasible region is called a feasible objective region. In multiobjective optimization, objective vectors are regarded as optimal if none of their components can be improved without deterioration to at least one of the other components. More precisely, a decision vector x 0 2 S is called Pareto optimal if there does not exist another x 2 S such that fi(x) 6 fi(x 0 ) for all i = 1, . . . , k and fj(x) < fj(x 0 ) for at least one index j. In addition, an objective vector is Pareto optimal if the corresponding decision vector is Pareto optimal. Under the assumptions mentioned in the problem formulation, we know that Pareto optimal solutions exist (see [24, Corollary 3.2.1]). The ranges of the Pareto optimal solutions in the feasible objective region provide valuable information about the problem considered if the objective functions are bounded over the feasible region. Lower bounds of the Pareto optimal set are available in

the ideal objective vector zw 2 Rk. Its components zH i are obtained by minimizing each of the objective functions individually subject to the feasible region. A vector strictly better than zw can be called a utopian objective vector zww. In practice, we set zHH ¼ zH i i e for i = 1, . . . , k, where e is some small positive scalar. The upper bounds of the Pareto optimal set, that is, the components of a nadir objective vector znad, are usually diﬃcult to obtain. Unfortunately, there exists no constructive way to obtain the exact nadir objective vector for nonlinear problems. It can be estimated using a payoﬀ table but the estimate may be unreliable (see e.g. [15] and references therein). In what follows, we assume that we have global estimates of the ranges of the Pareto optimal solutions available. Because vectors cannot be ordered completely, all the Pareto optimal solutions can be regarded as equally desirable in the mathematical sense and we need a decision maker to identify the most preferred one among them. The decision maker is a person who can express preference information related to the conﬂicting objectives and we assume that less is preferred to more in each objective for her/him.

3. Scalarizing functions and related subproblems To begin with, we lay a foundation for the synchronous approach to be described by introducing several classiﬁcation and reference point based scalarizing functions. These real-valued functions are formed based on the multiple objective functions and the preference information speciﬁed by the decision maker and they usually generate Pareto optimal solutions for the original problem. In this section, we introduce one new and three scalarizing functions from the literature. Let us ﬁrst describe what we mean by classiﬁcation and reference points. In classiﬁcation, the decision maker directs the interactive solution process in the set of Pareto optimal solutions. Objective function values calculated at the current Pareto optimal decision vector xc 2 S are presented to the decision maker. (S)he can then express what kind of changes would be desirable to her/him by classifying each of the objective functions into diﬀerent

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

classes. Here we consider ﬁve diﬀerent classes (used also in the NIMBUS method): functions fi in • I< whose values are desired to be improved (i.e., decreased) from the current level, • I6 whose values are desired to be improved till some desired aspiration level ^zi < fi ðxc Þ, • I = whose values are acceptable in the current solution, • IP whose values may be impaired (i.e., increased) till some upper bound ei > fi(xc), and • I whose values are temporarily allowed to change freely. The aspiration levels and the upper bounds corresponding to the classiﬁcation are elicited from the decision maker. In reference point based methods, the decision maker speciﬁes a reference point z 2 Rk consisting of desirable aspiration levels zi for each objective function. This reference point does not have to depend on the current solution. It only indicates what kind of objective function values the decision maker prefers. Note that usually the ideal objective vector (and possibly an approximation of the nadir objective vector) are calculated and presented to the decision maker before any classiﬁcation or reference point information is requested. This gives the decision maker some perspective about the possibilities and the limitations of the problem. Thus, we can assume that the decision maker does not specify hopes beyond the ideal values, in other words, we assume that zi P zH i for i = 1, . . ., k. If we know the ranges of the Pareto optimal set, we can form a reference point based on the classiﬁcation information given. In this case, we set < zi ¼ zH zi ¼ ^zi for i 2 I6, zi ¼ fi ðxc Þ for i for i 2 I , = i 2 I , zi ¼ ei for i 2 IP and zi ¼ znad for i 2 I. i Thus, the two ways of specifying preference information are closely related. A reliable and an understandable way of extracting preference information from the decision maker is an essential part of an interactive method. An example of an indirect and an unpredictable way of directing the solution process is employing weighting coeﬃcients. One can never predict how they aﬀect the solution obtained and

913

the weighted sum has no understandable meaning. For more details see, for example, [15] and references therein. On the contrary, asking the decision maker for a classiﬁcation or a reference point is a very straightforward way to obtain preference information. Because the decision maker deals with desirable objective function values, the information treated has a concrete and clearly understandable meaning. Thus, the decision maker does not have to master complicated concepts and it is easy to compare the eﬀect of the classiﬁcation in the resulting objective function values. The desirability of classiﬁcation as a tool of expressing preferences is demonstrated, for example, in [19]. The same conclusion can be drawn from practical applications like the ones in [9,20,21]. This conﬁrms the basic setting of the NIMBUS method. The NIMBUS method is based on classiﬁcation where the decision maker is in each iteration asked to classify the objective functions into up to the ﬁve above-deﬁned classes I<, I6, I=, IP and I. The idea is that in this way the decision maker directs the solution process in order to ﬁnd the most preferred Pareto optimal solution. That is why a classiﬁcation is feasible only if at least one of the objective functions should improve and at least one is allowed to increase from their current levels, that is, I< [ I6 5 ; and IP [ I 5 ;. In NIMBUS, a subproblem is formed based on the classiﬁcation and the corresponding aspiration levels and upper bounds. We present here a new subproblem formulation involving a somewhat different treatment of the class I6 when compared to the earlier NIMBUS variant presented in [15,17]. In addition, this subproblem has an augmentation term guaranteeing Pareto optimal results. To be more precise, we employ the subproblem "

minimize

fi ðxÞ zH fj ðxÞ ^zj i max ; nad nad HH < i2I zi zi zj zHH j 6

#

j2I

þq

k P i¼1

fi ðxÞ

zHH znad i i

subject to fi ðxÞ 6 fi ðxc Þ for all i 2 I < [ I 6 [ I ¼ ; fi ðxÞ 6 ei for all i 2 I P ; x 2 S; ð3:1Þ

914

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

where a so-called augmentation coeﬃcient q > 0 is a relatively small scalar. The weighting coeﬃcients 1=ðznad

zHH j j Þ have proven to facilitate capturing the preferences of the decision maker well. They also increase computational eﬃciency. Next, we introduce three subproblems where the scalarizing functions are based on reference points. Note that here we concentrate on the scalarizing functions and not the methods they originate from. Further details of the methods and the subproblems can be found in [15]. As mentioned earlier, reference points can be formed based on the classiﬁcation information without asking any additional information from the decision maker. Thus, these subproblems can be used in the NIMBUS method in addition to subproblem (3.1). The choice of these three subproblems to be considered is based on the results of [19] where 15 scalarizing functions were numerically and theoretically compared. The goal was to ﬁnd scalarizing functions that satisfy the preferences expressed by the decision maker well enough and still usually generate diﬀerent solutions. The question why the diﬀerent subproblems produce diﬀerent solutions even though they are based on the same preference information is theoretically considered in [19]. The results are there supported with numerical tests. The scalarizing function in the following subproblem comes from the satisﬁcing trade-oﬀ method (STOM) [23] k P fi ðxÞ zHH fi ðxÞ i minimize max þ q HH i¼1;...;k z zi zHH i¼1 i zi i subject to x 2 S; ð3:2Þ where the aspiration levels zi must be strictly higher than the corresponding components of the utopian objective vector zHH i . Achievement (scalarizing) functions have been introduced, for example, in [27] and they are used in the reference point method, among others. From the many variants of achievement functions, we use a basic formulation in the subproblem k P fi ðxÞ zi fi ðxÞ minimize max nad þq HH nad i¼1;...;k zi z

zi

zHH i¼1 i i subject to x 2 S: ð3:3Þ

It is interesting to note that if we set the denominator equal to zi zHH i , the resulting problem is actually equivalent to (3.2). The scalarizing function used in the last subproblem to be introduced is related to the one used in the GUESS method [3] k P fi ðxÞ znad fi ðxÞ i minimize max þq nad nad } zi zi

zi i62I i¼1 zi subject to x 2 S: ð3:4Þ In order to guarantee Pareto optimality, we include here an augmentation term that was not used in the original formulation. We also need to make some minor changes in the scalarizing function because our reference point originates from classiﬁcation and we must avoid dividing by zero. Thus, for i 2 I, we replace the denominator in the sum term by znad

zHH i i . Notice that the aspiration levels zi have to be strictly lower than the components of the nadir objective vector znad i . Even though this subproblem relies signiﬁcantly on the nadir objective vector, which has to be estimated, its success does not heavily depend on the correctness of the estimate (see [19]). When comparing subproblems (3.1)–(3.4), the most signiﬁcant diﬀerence is the presence of additional constraints in (3.1). With these constraints, we guarantee that objective functions to be decreased do not increase and the upper bounds speciﬁed are not violated. In other words, the classiﬁcation information is strictly obeyed in these respects. On the other hand, the other subproblems treat the information formulated as a reference point in a more suggestive way with no strict bounds. This diﬀerence in treating the preference information originates from the fact that classiﬁcation is based on the current solution whereas a reference point can be formed independently of the current solution. Even though we have here connected these two together, we do not wish to bind the functioning of the reference point based scalarizing functions by additional constraints. As far as the optimality of the solutions obtained by solving the four subproblems (3.1)– (3.4) is concerned, they are guaranteed to be

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

Pareto optimal because of the presence of the augmentation term. For further details related to (3.2)– (3.4), see [15]. Here we prove the result for (3.1). Theorem 3.1. The solution of (3.1) is Pareto optimal for (2.1). Proof. Let x* 2 S be the solution of (3.1). Let us assume that it is not Pareto optimal. In this case, there exists another x 0 2 S such that fi(x 0 ) 6 fi(x*) for all i = 1, . . . , k and the inequality is strict for at least one index j. This implies that x 0 is feasible for (3.1). We have "

fi ðx0 Þ zH fj ðx0 Þ ^zj i ; max i2I < znad

zHH znad

zHH i i j j j2I 6

"

#

fi ðx Þ zH fj ðx Þ ^zj i ; 6 max nad HH i2I < zi zi znad

zHH j j

#

j2I 6

and q

k X i¼1

k X fi ðx0 Þ fi ðx Þ < q : znad znad zHH

zHH i i i i¼1 i

Thus, x* cannot be a solution of (3.1). This contradiction implies the Pareto optimality of x*. h

4. Synchronous NIMBUS algorithm Next we describe a synchronous NIMBUS algorithm. In the earlier variants of the NIMBUS method [15–17], one subproblem was formed based on the classiﬁcation information provided by the decision maker. However, as described earlier, the same information can be the basis of several diﬀerent subproblems. Thus, we can solve several subproblems based on the preferences once expressed and let the decision maker select the most preferred solution. Besides directing the solution process in NIMBUS with classiﬁcation, the decision maker may also ask for a desired number of intermediate solutions to be generated between any two Pareto optimal solutions. In this case, steps of equal length are taken in the decision space and the correspond-

915

ing objective vectors are given as reference points to (3.3). This results with Pareto optimal solutions. Due to several subproblems and intermediate solutions, the amount of (Pareto optimal) solutions generated increases and, thus, a ﬂexible data management is important. For this reason, we provide a possibility for the decision maker to save solutions in a database. Let us formulate the basic steps of the synchronous NIMBUS algorithm. We denote the set of saved solutions by A. At ﬁrst, we set A = ;. The starting point of the solution process can come from the decision maker or it can be some neutral compromise [29] between the objectives. 1. Generate a Pareto optimal starting point. 2. Ask the decision maker to classify the objective functions at the current solution and to specify the possible aspiration levels and upper bounds. 3. Ask the decision maker to select the maximum number of diﬀerent solutions to be generated (between one and four) and solve as many subproblems (among (3.1)–(3.4)). 4. Present the diﬀerent new solutions obtained to the decision maker. 5. If the decision maker wants to save one or more of the new solutions to A, include it/them to A. 6. If the decision maker does not want to see intermediate solutions between any two solutions, go to step 8. Otherwise, ask the decision maker to select the two solutions from among the new solutions or the solutions in A. Ask the number of the intermediate solutions from the decision maker. 7. Generate the desired number of intermediate solutions and project them to the Pareto optimal set. Go to step 4. 8. Ask the decision maker to choose the most preferred one among the new and/or the intermediate solutions or the solutions in A. Denote it as the current solution. If the decision maker wants to continue, go to step 2. Otherwise, stop. Let us list a few comments related to the algorithm. The algorithm is terminated if the decision maker does not want to decrease any objective value or is not willing to let any objective value increase. Otherwise, the search continues iteratively

916

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

by moving around the Pareto optimal set. If desired, for example, the method presented in [28] could be used for proving convergence. Several subproblems are used in the synchronous NIMBUS algorithm for three main reasons. On one hand, the method developers do not have to ﬁx one scalarizing function and, thus, decide which of the resulting solutions captures the preferences of the decision maker best but it is up to the decision maker. On the other hand, several solutions giving a more versatile image of the Pareto optimal set are calculated without artiﬁcially altering the preference information given by the decision maker. Usually, interactive methods that generate a set of diﬀerent Pareto optimal solutions are based on altering the preference information in one way or the other as mentioned in the introduction, and we avoid that. The third advantage of using several subproblems is that they treat the same preference information in diﬀerent ways. For example, subproblem (3.1) obeys the upper bound constraints of class IP strictly whereas the other subproblems may exceed them (each, in different ways). If, for example, it is not possible to generate a new solution with the presence of strict constraints, having the other solutions available gives the decision maker a possibility to see what kind of increments would be needed in order to achieve the improvements desired. Thus, the decision maker can continue the solution process instead of having to go back and to try another classiﬁcation with relaxed upper bounds. Versatility is the most important characteristic of the NIMBUS algorithm. The decision maker has a variety of strategies available for directing the interactive solution process. If (s)he does not like to compare solutions, (s)he can use only the classiﬁcation and one subproblem and decide at each iteration whether to continue with the current or the new solution. Alternatively (s)he can have a look at representatives from the Pareto optimal set and employ several subproblems and intermediate solutions. Flexibility in the algorithm implies that the decision maker is free to change the strategy from one iteration to the next, if desired. In other words, the previous choices do not limit her/his movements. The synchronous approach is suitable for such decision makers who are willing to see dif-

ferent solutions without specifying additional preference information. Note that the solutions generated using diﬀerent subproblems or as intermediate solutions are not all necessarily diﬀerent [19]. In this case, we only show the diﬀerent ones. It may even happen that all the subproblems lead to the same solution. This can be regarded as an indication of robustness in the subproblems, which is a valuable piece of information in itself and not a drawback. The synchronous NIMBUS method has been used for solving complex problems related to the designing of paper machines [13] and planning paper making processes [8]. The experts who have acted as decision makers have expressed their appreciation for the versatility of the synchronous approach (when compared, for example, to the earlier variants of NIMBUS). They have obtained a better picture of the possibilities of the problem without having to input too much preference information. By studying the solutions of the different scalarizing functions, the decision makers have had a chance to learn about the problems in a new way and compare what kind of solutions can be obtained when the classiﬁcation information is utilized with varied degrees of strictness. This speeds up the interactive solution process when more can be learnt during each iteration and, thus, less iterations are needed.

5. WWW-NIMBUS The structure of the interactive NIMBUS algorithm does not limit the variety of its applications in the area of multiobjective optimization. The only limiting factor in practice is the underlying single objective optimizer that has to be able to handle the subproblems and the possible special features of the problem to be solved. As mentioned in the introduction, an implementation WWWNIMBUS [18] of the NIMBUS method is available on the Internet at http://nimbus.mit.jyu.ﬁ/. Next, we describe some features of the version 4.0 of WWW-NIMBUS. WWW-NIMBUS is based on the ideas of centralized computing and distributed interface. Because WWW-NIMBUS operates via the Internet,

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

it sets no requirements on the operating system used or the compilers available. In other words, it does not have to be downloaded and, for this reason, latest version is always available. WWWNIMBUS generates html-pages based on the input of the user. To be more speciﬁc, it can generate over 20 diﬀerent pages along the solution process. In addition, the system contains a tutorial and each page has an individual help page. Personal usernames and passwords guarantee that problems can be saved and loaded in the system. WWW-NIMBUS has been designed for solving nonlinear (and even nondiﬀerentiable and nonconvex) multiobjective optimization problems because there is an evident need for such software. The objective functions may be minimized or maximized and the feasible region S may consist of nonlinear and linear inequality and equality constraints as well as lower and upper bounds for the variables. The problem to be solved can be speciﬁed for the system either by completing a web form or by preparing a subroutine. The latter option makes it possible to solve even complex problems without analytic function formulations. The solution where the user is asked to classify the objective functions for the ﬁrst time is generated by using the subproblem (3.3) with zi ¼ ðznad i þ zHH Þ=2 as aspiration levels for i = 1, . . ., k. The rei sult is a so-called neutral compromise solution [29]. It is a good starting point when no preference information is yet available. The next step, the classiﬁcation of the objective functions, can be carried out either symbolically using radiobuttons or graphically by indicating desirable changes in a bar chart with a mouse. The bars include information about the current objective values as well as the ranges of each objective function in the Pareto optimal set. After the classiﬁcation, the user can select how many diﬀerent solutions (s)he wants to see and as many corresponding subproblems are formed based on the classiﬁcation information. They can be solved with diﬀerent underlying optimizers and the decision maker may select after each classiﬁcation, which optimizer is to be used. Both a local and a global solver are available in the current version of WWW-NIMBUS. If the user wishes to

917

use a local solver, it is possible to select the proximal bundle method. This method can solve even nondiﬀerentiable problems and it assumes the objective and the constraint functions to be locally Lipschitz continuous. Note that it needs (sub)gradient information. For further details, see [14]. If the problem has been speciﬁed using the web form, the user does not have to derive (sub)gradients because the software contains a symbolic (sub)diﬀerentiator. Alternatively, the user can select a genetic algorithm as a global solver. In this case, the problem to be solved may also contain integer-valued variables. In their basic form, genetic algorithms are not capable of handling linear and nonlinear constraints eﬃciently. Yet, this is required in our subproblems. For this reason, WWW-NIMBUS contains two variants of genetic algorithms with diﬀerent constraint-handling techniques [22]. One of them is based on adaptive penalties [7] and the other can be called a method of parameter free penalties [6]. (Let us mention that if (sub)gradient information is available, we call the local solver after the global one and with this simple hybrid method guarantee the optimality of the ﬁnal solution.) All the optimizers contain technical parameters and the user can change their default values, if necessary. If the user of WWW-NIMBUS does not know whether to use a local or a global solver, it is advisable to mainly use the faster local solver and every now and then the global solver to check whether nonconvexities have caused the solutions to get trapped in local optima. The two diﬀerent constraint-handling techniques for the genetic algorithm are available so that the user can compare their performances, if desired. Otherwise, the method of parameter free penalties is recommended because it involves no additional parameters, as its name suggests. The system generates a desired number of new solutions after each classiﬁcation and the number of alternative solutions increases if the user asks for intermediate solutions. Thus, the comparison of diﬀerent solutions is important. Note that the user can save interesting solutions in a solution database at any time. The comparison task between new and/or saved solutions is facilitated

918

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

using visualizations of the alternatives. The user can select the visualizations to be displayed among bar charts, value paths and petal diagrams. Both absolute and relative scales can be used in the visualizations. The user can also drop some of the alternatives from further consideration in this phase. As far as WWW-NIMBUS is concerned in general, the user can save, load and modify problems. The ﬂexible database management enables saving selected solutions whenever required. In this way, the user can comfortably return to previous solutions if they turn out to be interesting, after all. The user can also easily graphically illustrate a (sub)set of saved solutions, and generate intermediate solutions between any two solutions. Because

of the structure of the implementation, all the solutions handled are Pareto optimal.

6. Numerical example Next we demonstrate the ideas of the synchronous NIMBUS algorithm by a simple example. It was solved using the WWW-NIMBUS system. We demonstrate the functioning of the WWWNIMBUS system by some displays of the solution process. We have six objective functions and bounds for the two variables as can be seen in Fig. 1. The ﬁrst objective function is to be maximized and all the others are to be minimized. In this problem, all the variables are continuous.

Fig. 1. Problem description in WWW-NIMBUS.

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

After specifying the problem formulation for WWW-NIMBUS, it generated the display in Fig. 2. This display contains the starting point for the classiﬁcation as well as estimated ranges of the Pareto optimal set. WWW-NIMBUS contains two possibilities for carrying out the classiﬁcation phase. The ﬁrst classiﬁcation using the symbolic way can be seen in Fig. 2. As can be seen in Fig. 2, the values of the second, the ﬁfth and the sixth objective function were to be decreased and relaxed bounds were speciﬁed for the others. The system was asked to generate no more than two new solutions. The speciﬁcation of the classiﬁcation parameters is shown in Fig. 3. Because an aspiration level must be between the current and the ideal objective values, these values can be seen in Fig. 3 for the second objective function. Correspondingly, the

Fig. 3. Specifying NIMBUS.

classiﬁcation

Fig. 2. Symbolic classiﬁcation in WWW-NIMBUS.

parameters

919

in

WWW-

920

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

the four new solutions are presented in Fig. 5 in the form of a petal diagram and a value path. This ﬁgure also gives an example of the visualization possibilities of WWW-NIMBUS. Any of these solutions could be selected as the ﬁnal solution or as the starting point of the next classiﬁcation. We stop the solution process here because the idea was only to demonstrate the functioning of the method. We learned about the behaviour of the objective functions and about their conﬂicting nature. Even though only two classiﬁcations were made, we were able to get versatile information about the problem.

7. Conclusions

Fig. 4. Results after the ﬁrst classiﬁcation.

current and the nadir objective values form bounds for functions that are allowed to impair. The starting point of the classiﬁcation as well as two new solutions generated based on the classiﬁcation can be seen in Fig. 4. One can see that it was not possible to decrease the values of the ﬁfth and the sixth objective function simultaneously. Thus, it was justiﬁed to have a look at intermediate solutions between them and two new solutions were generated. They were (4.6, 7.2, 4.3, 0.2, 1450.0, 1805.6) and (4.5, 7.2, 4.3, 0.2, 1434.7, 1822.5). The ﬁrst of these was selected as the starting point of the next classiﬁcation. In the second classiﬁcation, the second and the sixth objective function were to be decreased, the ﬁrst one was allowed to change freely and upper bounds were given to the rest of the functions. To be more speciﬁc, we set I< = {6}, I6 = {2}, IP = {3,4,5} and I={1} with ^z2 ¼ 4:0, e3 = 3.0, e4 = 1.0 and e5 = 1600.0. The system was asked to generate up to four new solutions. The starting point of the classiﬁcation as well as

Our motivation in this work has been to encourage method developers to take into account the important fact that selecting the scalarizing function and the subproblem used in multiobjective optimization really plays a signiﬁcant role. In this paper, we have introduced a new approach in creating interactive methods. This approach is based on the fact that classiﬁcation and reference point based scalarizing functions are closely related. In other words, the preference information obtained from the decision maker can be used to form diﬀerent subproblems and to generate several Pareto optimal solutions. In this way, the decision maker can decide her/himself which of the solutions obtained satisﬁes the preferences best. Simultaneously, in the synchronous approach, the decision maker obtains a better view of the potential compromises based on the preference input once expressed. If it happens that the diﬀerent subproblems all lead to the same solution, this is an indication of robustness in the scalarization functions, which is a valuable piece of information in itself. We have described a synchronous variant of the interactive NIMBUS method. To be more precise, we have introduced a new scalarizing function and incorporated three other scalarizing functions into the method to provide a more versatile view of the behaviour of the problem considered. In addition, the implementation of the synchronous NIMBUS algorithm in the WWW-NIMBUS system operat-

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

921

Fig. 5. Visualization of alternatives in WWW-NIMBUS.

ing on the Internet has been described. The consideration of several alternative solutions brings along the need of eﬃcient database management. This issue has also been treated in the new version 4.0 of WWW-NIMBUS. The other new features of version 4.0 include the possibility of dealing with maximization as well as handling equality constraints. So far, the experiences related to the performance of the new method and the ideas introduced here have been positive for both academic and demanding real-life problems.

Acknowledgements This research was supported by the National Technology Agency of Finland. The authors wish to thank Mr. Jari Huikari and Mr. Vesa Ojalehto

for their share in the implementation of WWWNIMBUS.

References [1] M.S. Bazaraa, H.D. Sherali, C.M. Shetty, Nonlinear Programming: Theory and Algorithms, second ed., John Wiley & Sons, New York, 1993. [2] R. Benayoun, J. de Montgolﬁer, J. Tergny, O. Laritchev, Linear programming with multiple objective functions: Step method (STEM), Mathematical Programming 1 (3) (1971) 366–375. [3] J.T. Buchanan, A naı¨ve approach for solving MCDM problems: the GUESS method, Journal of the Operational Research Society 48 (1997) 202–206. [4] J. Buchanan, L. Gardiner, A comparison of two reference point methods in multiple objective mathematical programming, European Journal of Operational Research 149 (2003) 17–34.

922

K. Miettinen, M.M. Ma¨kela¨ / European Journal of Operational Research 170 (2006) 909–922

[5] V. Chankong, Y.Y. Haimes, Multiobjective Decision Making Theory and Methodology, Elsevier, New York, 1983. [6] K. Deb, An eﬃcient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering 186 (2000) 311–338. [7] A.B. Hadj-Alouane, J.C. Bean, A genetic algorithm for the multiple-choice integer program, Operations Research 45 (1) (1997) 92–101. [8] J. Hakanen, K. Miettinen, M.M. Ma¨kela¨, An application of multiobjective optimization to process simulation, in: P. Neittaanma¨ki, T. Rossi, S. Korotov, E. On˜ate, J. Pe´riaux, D. Kno¨rzer (Eds.), Proceedings of the 4th European Congress on Computational Methods in Applied Sciences and Engineering, ECCOMAS2004, CD, vol. II, 2004. [9] J. Ha¨ma¨la¨inen, K. Miettinen, P. Tarvainen, J. Toivanen, Interactive solution approach to a multiobjective optimization problem in paper machine headbox design, Journal of Optimization Theory and Applications 116 (2) (2003) 265–281. [10] L.R. Gardiner, R.E. Steuer, Uniﬁed interactive multiple objective programming, European Journal of Operational Research 74 (3) (1994) 391–406. [11] C.-L. Hwang, A.S.M. Masud, Multiple Objective Decision Making––Methods and Applications, Springer-Verlag, Berlin, Heidelberg, 1979. [12] P. Korhonen, J. Laakso, A visual interactive method for solving the multiple criteria problem, European Journal of Operational Research 24 (1986) 277–287. [13] E. Madetoja, On interactive multiobjective optimization related to paper quality, Licentiate Thesis, University of Jyva¨skyla¨, Jyva¨skyla¨, 2003. [14] M.M. Ma¨kela¨, P. Neittaanma¨ki, Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control, World Scientiﬁc Publishing Co., Singapore, 1992. [15] K. Miettinen, Nonlinear Multiobjective Optimization, Kluwer Academic Publishers, Boston, 1999. [16] K. Miettinen, M.M. Ma¨kela¨, Interactive bundle-based method for nondiﬀerentiable multiobjective optimization: NIMBUS, Optimization 34 (3) (1995) 231–246. [17] K. Miettinen, M.M. Ma¨kela¨, Comparative evaluation of some interactive reference point-based methods for multiobjective optimisation, Journal of the Operational Research Society 50 (1999) 949–959. [18] K. Miettinen, M.M. Ma¨kela¨, Interactive multiobjective optimization system WWW-NIMBUS on the Internet,

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27] [28]

[29]

Computers & Operations Research 27 (7–8) (2000) 709–723. K. Miettinen, M.M. Ma¨kela¨, On scalarizing functions in multiobjective optimization, OR Spektrum 24 (2002) 193–213. K. Miettinen, M.M. Ma¨kela¨, R.A.E. Ma¨kinen, Interactive multiobjective optimization system NIMBUS applied to nonsmooth structural design problems, in: J. Dolezˇal, J. Fidler (Eds.), System Modelling and Optimization, Chapman & Hall, London, 1996, pp. 379–385. K. Miettinen, M.M. Ma¨kela¨, T. Ma¨nnikko¨, Optimal control of continuous casting by nondiﬀerentiable multiobjective optimization, Computational Optimization and Applications 11 (1998) 177–194. K. Miettinen, M.M. Ma¨kela¨, J. Toivanen, Numerical comparison of some penalty-based constraint handling techniques in genetic algorithms, Journal of Global Optimization 27 (4) (2003) 427–446. H. Nakayama, Y. Sawaragi, Satisﬁcing trade-oﬀ method for multiobjective programming, in: M. Grauer, A.P. Wierzbicki (Eds.), Interactive Decision Analysis, Springer Verlag, Berlin, 1984, pp. 113–122. Y. Sawaragi, H. Nakayama, T. Tanino, Theory of Multiobjective Optimization, Academic Press, Inc., Orlando, Florida, 1985. R.E. Steuer, The Tchebycheﬀ procedure of interactive multiple objective programming, in: B. Karpak, S. Zionts (Eds.), Multiple Criteria Decision Making and Risk Analysis Using Microcomputers, Springer-Verlag, Berlin, Heidelberg, 1989, pp. 235–249. V. Vassilev, S.C. Narula, V.G. Gouljashki, An interactive reference direction algorithm for solving multi-objective convex nonlinear integer programming problems, International Transactions in Operational Research 8 (4) (2001) 367–380. A.P. Wierzbicki, A mathematical basis for satisﬁcing decision making, Mathematical Modelling 3 (1982) 391–405. A.P. Wierzbicki, Convergence of interactive procedures of multiobjective optimization and decision support, in: M.H. Karwan, J. Spronk, J. Wallenius (Eds.), Essays in Decision Making: A Volume in Honour of Stanley Zionts, SpringerVerlag, Berlin, Heidelberg, 1997, pp. 19–47. A.P. Wierzbicki, Reference point approaches, in: T. Gal, T.J. Stewart, T. Hanne (Eds.), Multicriteria Decision Making: Advances in MCDM Models, Algorithms, Theory, and Applications, Kluwer Academic Publishers, Boston, 1999, pp. 9-1–9-39.