by
Kaisa
Miettinen
Department
of Mathematical Information Technology
P.O. Box
35 (Agora), FIN-40014
University
of Jyväskylä, Finland
miettine@mit.jyu.fi
Introduction
Software
for solving multiobjective optimization problems is not easy to find. The task
gets even more difficult if the problem involves nonlinear functions. WWW-NIMBUS
[8], an interactive software system operating on the Internet, has been
developed to answer this need. It can be used for solving nonlinear and even
nondifferentiable and nonconvex multiobjective optimization problems. Because
the Internet is easily accessible, the system is automatically available to
large numbers of people. In 1995, the first version of WWW-NIMBUS was the first
interactive multiobjective optimization software operating on the Internet. Even
now, when version 3.3 of WWW-NIMBUS is available at http://nimbus.mit.jyu.fi/ it
continues to be a unique software system. WWW-NIMBUS has changed quite a lot
during the years but it can still be used free of charge for teaching and
academic research proposes.
WWW-NIMBUS
is based on the principles of centralized computing and distributed interface.
This means that all the calculations take place in a server computer at the
University of Jyväskylä and the user interface is the browser of each
individual user. In this way, the system sets no requirements on the user's
computer and the operating system used and/or compilers available play no role.
There is nothing to be installed and the latest version of the system is always
available. Furthermore, the World-Wide Web (WWW) provides a convenient and
graphical user interface with visualization possibilities.
The
NIMBUS method is the core of WWW-NIMBUS. NIMBUS (Nondifferentiable Interactive
Multiobjective BUndle-based optimization System) is an interactive method where
preference information is acquired from the decision maker in the form of a
classification of the objective functions. The method has been applied, for
example, in structural design problems [11], in the optimal control problems of
the continuous casting of steel [12]
and in the optimal shape design of paper machine headboxes [3]. Results with
both small-scale and large-scale problems give evidence of the reliability and
efficiency of the method. Different versions of NIMBUS are described in [5,6,
7]. Here we concentrate on the latest, so-called synchronous, version [10].
In
NIMBUS, the decision maker can iteratively learn about the problem and can
conveniently direct the solution process. NIMBUS has been designed to be easy to
use and, unlike many interactive methods, it does not require consistent
information from the decision maker. Furthermore, the information handled is
straightforward. The objective function values have a direct meaning to the
decision maker and no artificial concepts are needed.
NIMBUS Method
The
multiobjective optimization problems to be considered are of the form
with
k objective
functions
to be minimized simultaneously. The
decision vector
belongs to the (nonempty) compact feasible
set S. The images of the feasible
decision vectors are called feasible objective
vectors.
The
idea of the interactive NIMBUS method is to move around the set of Pareto
optimal solutions. Thus, we need information about the ranges of the feasible
objective vectors in the Pareto optimal set. We refer to the best values of each
objective function as their ideal values.
In
the interactive solution process, the decision maker can at each iteration
indicate what kind of a solution would be more satisfactory than the current
with the help of a classification. Thus, the user can evaluate the problem to be
solved and adapt one's preferences during the solution process in an iterative
and flexible way. Let
stand for the Pareto optimal
decision vector at the iteration h.
Then the decision maker is asked to classify the objective functions into up to
five classes for objective functions
whose values should be decreased
, should be decreased till some aspiration level
, are satisfactory at the moment
, are allowed to increase till some upper bound
and are allowed to change freely
.
The
difference between the first two classes is that the objective functions in the
first class are to be minimized as far as possible but the functions in the
second class only till the aspiration level specified. The decision maker is
asked to specify the aspiration levels and upper bounds, if needed. Since
improvement in the Pareto optimal set in any objective function value is
possible only by allowing
impairment in some other objective function, the classification is feasible only
if neither
nor
is empty.
After
the classification, a subproblem
[8] is formed based on the information specified as
where
are the ideal objective values. We set
for some small positive scalar
. Otherwise, we set
.
As
shown in [9], different subproblems may lead to different solutions even though
they are based on the same preference information. Usually method developers
select one subproblem, which means that they select the solution to be
generated. Yet, there is no general way how to identify the best solution
without involving the decision maker.
In
the synchronous version of NIMBUS [10], there are three subproblems available in
addition to (1). This means that if the decision maker wants so, (s)he can see
up to four different solutions after one classification. In other words, by
classifying the objective functions once, the decision maker can get a better
picture of different Pareto optimal solutions satisfying the preference
information specified. Besides, the method developers do not have to make the
choice related to the subproblem. Based on the experiments and comparison of
different subproblems [9], we have selected subproblems extracted from the STOM,
GUESS and Wierzbicki's reference point methods (see, e.g. [7]). They all involve
reference point information that can be derived from the classification.
In
NIMBUS, the decision maker can also explore a desired number of intermediate
solutions between any two solutions. Note that the solutions generated using
different subproblems or as intermediate solutions are not all necessarily
different [9]. In this case, we only show the different ones.
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 by moving around the Pareto optimal
set.
WWW-NIMBUS System
available at http://nimbus.mit.jyu.fi
The
WWW-NIMBUS system is capable of solving nonlinear problems involving even
nondifferentiable and nonconvex functions where the variables can be continuous
or integer-valued. The constraints may be linear, nonlinear or bounds for
variables.
Personal
usernames and passwords enable saving and handling private problems so that the
user can return to them later. One can also visit WWW-NIMBUS as a guest but then
it is not possible to save any problems to the system. Each page of WWW-NIMBUS
has an individual help page. The system has also a tutorial.
The
problem to be solved can be specified either by filling a web form or by
preparing a Fortran subroutine. The possibility of specifying the problem as a
subroutine enables the solution of large-scale problems and/or problems that do
not have explicit formulas of functions. (However, this possibility is available
for local users only.)
After
the optimization problem has been specified, the starting point, either given by
the decision maker or generated automatically by the system, is projected onto
the Pareto optimal set. This point is the basis of the first classification. The
classification of the objective functions can be carried out either symbolically
or graphically by indicating desirable values in a bar chart with a mouse. The
bars include information about the current objective values as well as the
estimated ranges of each objective function in the Pareto optimal set.
After
the classification, the user selects the maximum number (between one and four)
of different new solutions to be generated. The system produces them by solving
different subproblems using some of the underlying optimizers. The user can
select the optimizer for each iteration individually. If the user wishes to use
a computationally efficient local solver, it is possible to use the proximal
bundle method [4]. This method can solve even nondifferentiable problems but it
assumes the objective and the constraint functions to be locally Lipschitz
continuous and it needs (sub)gradient information. If the problem has been
specified using the web form, the user does not have to derive (sub)gradients
because the software contains a symbolic (sub)differentiator.
If
the user prefers global optimization, (s)he can select between two variants of
genetic algorithm. In this case, the problem to be solved may contain also
integer-valued variables. The two variants use different constraint-handling
techniques. One of them is based on adaptive penalties [2] and the other is a
method of parameter free penalties [1]. All the optimizers contain technical
parameters and the user can change the default values, if necessary.
Whenever
the user attains an interesting solution (s)he can save it in a solution
database. This means that the user can comfortably return to previous solutions
if they turn out to be interesting, after all. The comparison task between any
set of solutions is facilitated by using visualizations of the alternatives. The
user can select between bar charts, value paths and petal diagrams in both
absolute and relative scales. The user can also drop some of the alternatives
from further consideration.
In
the implementation of WWW-NIMBUS, the goal has been to keep the system as
general as possible. This means that special features available only in certain
browsers have been avoided. The size of the problems that can be solved has not
been limited in the implementation.
WWW-NIMBUS
opens up a worldwide possibility for any Internet user to utilize the
achievements of the Optimization Group (http://www.mit.jyu.fi/optgroup/) working
at the University of Jyväskylä.
Acknowledgements
The
research was supported by the Academy of Finland (grant #65760) and the National
Technology Agency of Finland. The author wishes to thank Dr. Marko M. Mäkelä
for his share in developing NIMBUS and WWW-NIMBUS as well as Jari Huikari and
Vesa Ojalehto for maintaining WWW-NIMBUS.
References
1.
K. Deb, An
Efficient Constraint Handling Method for Genetic Algorithms, Computer
Methods in Applied Mechanics and Engineering,186 (2000) 311-338.
2.
A.B. Hadj-Alouane and J.C. Bean, A Genetic Algorithm for the
Multiple-Choice Integer Program, Operations
Research, 45(1) (1997) 92-101.
3.
J.P. Hämäläinen, K. Miettinen, P. Tarvainen and 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.
4.
M.M. Mäkelä and P. Neittaanmäki, Nonsmooth
Optimization: Analysis and Algorithms with Applications to Optimal Control,
World Scientific Publishing Co., Singapore, 1992.
5.
K. Miettinen, Nonlinear
Multiobjective Optimization, Kluwer Academic Publishers, Boston, 1999.
6.
K. Miettinen and M.M. Mäkelä, Interactive Bundle-Based Method for
Nondifferentiable Multiobjective Optimization: NIMBUS, Optimization,
34(3) (1995) 231-246.
7.
K. Miettinen and M.M. Mäkelä, Comparative Evaluation of Some
Interactive Reference Point-Based Methods for Multi-Objective Optimisation, Journal of the Operational Research Society, 50(9) (1999), 949-959.
8.
K. Miettinen and M.M. Mäkelä, Interactive Multiobjective Optimization
System WWW-NIMBUS on the Internet, Computers
& Operations Research, 27(7-8) (2000) 709-723.
9.
K. Miettinen and M.M. Mäkelä, On Scalarizing Functions in
Multiobjective Optimization, OR Spectrum,
24(2) (2002) 193-213.
10.
K. Miettinen and M.M. Mäkelä, Synchronous Scalarizing Functions within
the Interactive NIMBUS Method for Multiobjective Optimization,
Reports of the Department of
Mathematical Information Technology, Series B, Scientific Computing, No. B
9/2002, University of Jyväskylä, Jyväskylä, 2002.
11.
K. Miettinen, M.M. Mäkelä and R.A.E. Mäkinen, Interactive
Multiobjective Optimization System NIMBUS Applied to Nonsmooth Structural Design
Problems, in: J. Dolezal, J. Fidler (Eds.), System
Modelling and Optimization, Chapman & Hall, London, 1996, pp.379-385.
12.
K. Miettinen, M.M. Mäkelä and T. Männikkö, Optimal Control of
Continuous Casting by Nondifferentiable Multiobjective Optimization, Computational Optimization and Applications, 11(2) (1998) 177-194.