NAUTILUS method: An interactive technique in multiobjective optimization based on the nadir point

Most interactive methods developed for solving multiobjective optimization problems sequentially generate Pareto optimal or nondominated vectors and the decision maker must always allow impairment in at least one objective function to get a new solution. The NAUTILUS method proposed is based on the assumptions that past experiences affect decision makers’ hopes and that people do not react symmetrically to gains and losses. Therefore, some decision makers may prefer to start from the worst possible objective values and to improve every objective step by step according to their preferences. In NAUTILUS, starting from the nadir point, a solution is obtained at each iteration which dominates the previous one. Although only the last solution will be Pareto optimal, the decision maker never looses sight of the Pareto optimal set, and the search is oriented so that (s)he progressively focusses on the preferred part of the Pareto optimal set. Each new solution is obtained by minimizing an achievement scalarizing function including preferences about desired improvements in objective function values. NAUTILUS is specially suitable for avoiding undesired anchoring effects, for example in negotiation support problems, or just as a means of finding an initial Pareto optimal solution for any interactive procedure. An illustrative example demonstrates how this new method iterates.     

A conic scalarization method in multi-objective optimization

This paper presents the conic scalarization method for scalarization of nonlinear multi-objective optimization problems. We introduce a special class of monotonically increasing sublinear scalarizing functions and show that the zero sublevel set of every function from this class is a convex closed and pointed cone which contains the negative ordering cone. We introduce the notion of a separable cone and show that two closed cones (one of them is separable) having only the vertex in common can be separated by a zero sublevel set of some function from this class. It is shown that the scalar optimization problem constructed by using these functions, enables to characterize the complete set of efficient and properly efficient solutions of multi-objective problems without convexity and boundedness conditions. By choosing a suitable scalarizing parameter set consisting of a weighting vector, an augmentation parameter, and a reference point, decision maker may guarantee a most preferred efficient or properly efficient solution.     

g-dominance: Reference point based dominance for multiobjective metaheuristics

One of the main tools for including decision maker (DM) preferences in the multiobjective optimization (MO) literature is the use of reference points and achievement scalarizing functions [A.P. Wierzbicki, The use of reference objectives in multiobjective optimization, in: G. Fandel, T. Gal (Eds.), Multiple-Criteria Decision Making Theory and Application, Springer-Verlag, New York, 1980, pp. 469–486.]. The core idea in these approaches is converting the original MO problem into a single-objective optimization problem through the use of a scalarizing function based on a reference point. As a result, a single efficient point adapted to the DM’s preferences is obtained. However, a single solution can be less interesting than an approximation of the efficient set around this area, as stated for example by Deb in [K. Deb, J. Sundar, N. Udaya Bhaskara Rao, S. Chaudhuri, Reference point based multiobjective optimization using evolutionary algorithms, International Journal of Computational Intelligence Research, 2(3) (2006) 273–286]. In this paper, we propose a variation of the concept of Pareto dominance, called g-dominance, which is based on the information included in a reference point and designed to be used with any MO evolutionary method or any MO metaheuristic. This concept will let us approximate the efficient set around the area of the most preferred point without using any scalarizing function. On the other hand, we will show how it can be easily used with any MO evolutionary method or any MO metaheuristic (just changing the dominance concept) and, to exemplify its use, we will show some results with some state-of-the-art-methods and some test problems.     

Using aspiration levels in an interactive interior multiobjective linear programming algorithm

In this paper, we propose the use of an interior-point linear programming algorithm for multiple objective linear programming (MOLP) problems. At each iteration, a Decision Maker (DM) is asked to specify aspiration levels for the various objectives, and an achievement scalarizing function is applied to project aspiration levels onto the nondominated set. The interior-point algorithm is used to find an interior solution path from a starting solution to a nondominated solution corresponding to the optimum of the achievement scalarizing function. The proposed approach allows the DM to re-specify aspiration levels during the solution process and thus steer the interior solution path toward different areas in objective space. We illustrate the use of the approach with a numerical example.     

A classification of the weighting schemes in reference point procedures for multiobjective programming

The reference point-based methods form one of the most widely used class of interactive procedures for multiobjective programming problems. The achievement scalarizing functions used to determine the solutions at each iteration usually include weights. In this paper, we have analysed nine weighting schemes from the preferential point of view, that is, examining their performance in terms of which reference values are given more importance and why. As a result, we have carried out a systematic classification of the schemes attending to their preferential meaning. This way, we distinguish pure normalizing schemes from others where the weights have a preferential interpretation. This preferential behaviour can be either designed (thus, predetermined) by the method, or decided by the decision maker. Besides, several figures have been used to illustrate the way each scheme works. This paper enables the potential users to choose the most appropriate scheme for each case.     

Reference point method with importance weighted ordered partial achievements

The Reference Point Method (RPM) is a very convenient technique for interactive analysis of the multiple criteria optimization problems. The interactive analysis is navigated with the commonly accepted control parameters expressing reference levels for the individual objective functions. The partial achievement functions quantify the DM satisfaction from the individual outcomes with respect to the given reference levels, while the final scalarizing achievement function is built as the augmented max–min aggregation of the partial achievements. In order to avoid inconsistencies caused by the regularization, the max–min solution may be regularized by the Ordered Weighted Averages (OWA) with monotonic weights which combines all the partial achievements allocating the largest weight to the worst achievement, the second largest weight to the second worst achievement, and so on. Further, following the concept of the Weighted OWA (WOWA), the importance weighting of several achievements may be incorporated into the RPM. Such a WOWA RPM approach uses importance weights to affect achievement importance by rescaling accordingly its measure within the distribution of achievements rather than by straightforward rescaling of achievement values. The recent progress in optimization methods for ordered averages allows one to implement the WOWA RPM quite effectively as extension of the original constraints and criteria with simple linear inequalities. There is shown that the OWA and WOWA RPM models meet the crucial requirements with respect to the efficiency of generated solutions as well as the controllability of interactive analysis by the reference levels.     

Multi-choice goal programming formulation based on the conic scalarizing function

The multi-choice goal programming allows the decision maker to set multi-choice aspiration levels for each goal to avoid underestimation of the decision. In this paper, we propose an alternative multi-choice goal programming formulation based on the conic scalarizing function with three contributions: (1) the alternative formulation allows the decision maker to set multi-choice aspiration levels for each goal to obtain an efficient solution in the global region, (2) the proposed formulation reduces auxiliary constraints and additional variables, and (3) the proposed model guarantees to obtain a properly efficient (in the sense of Benson) point. Finally, to demonstrate the usefulness of the proposed formulation, illustrative examples and test problems are included.     

Synchronous approach in interactive multiobjective optimization

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 classification of objective functions. The idea is to formulate several scalarizing functions, all using the same preference information of the decision maker. Thus, opposed to fixing 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 different scalarizing functions but calculate the results of different scalarizing functions and leave the final 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.     

Using cutting planes in an interactive reference point approach for multiobjective integer linear programming problems

We propose an interactive approach for multiple objective integer linear programming (MOILP) problems that combines the use of the Tchebycheff metric with cutting plane techniques. At each interaction, the method computes the nondominated solution for the MOILP problem that is closest to a reference point according to the Tchebycheff metric. The information provided by the decision maker in each dialogue phase is used to adjust the next reference point through a sensitivity analysis stage. Cutting plane techniques enable the method to take advantage of computations performed at previous iterations to solve the next scalarizing integer program. We address both theoretical issues and the computational implementation.     

A Post-Optimality Analysis Algorithm for Multi-Objective Optimization

Algorithms for multi-objective optimization problems are designed to generate a single Pareto optimum (non-dominated solution) or a set of Pareto optima that reflect the preferences of the decision-maker. If a set of Pareto optima are generated, then it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optima using an unbiased technique of filtering solutions. This suggests the need for an efficient selection procedure to identify such a preferred subset that reflects the preferences of the decision-maker with respect to the objective functions. Selection procedures typically use a value function or a scalarizing function to express preferences among objective functions. This paper introduces and analyzes the Greedy Reduction (GR) algorithm for obtaining subsets of Pareto optima from large solution sets in multi-objective optimization. Selection of these subsets is based on maximizing a scalarizing function of the vector of percentile ordinal rankings of the Pareto optima within the larger set. A proof of optimality of the GR algorithm that relies on the non-dominated property of the vector of percentile ordinal rankings is provided. The GR algorithm executes in linear time in the worst case. The GR algorithm is illustrated on sets of Pareto optima obtained from five interactive methods for multi-objective optimization and three non-linear multi-objective test problems. These results suggest that the GR algorithm provides an efficient way to identify subsets of preferred Pareto optima from larger sets.     

A parallel multiple reference point approach for multi-objective optimization

This paper presents a multiple reference point approach for multi-objective optimization problems of discrete and combinatorial nature. When approximating the Pareto Frontier, multiple reference points can be used instead of traditional techniques. These multiple reference points can easily be implemented in a parallel algorithmic framework. The reference points can be uniformly distributed within a region that covers the Pareto Frontier. An evolutionary algorithm is based on an achievement scalarizing function that does not impose any restrictions with respect to the location of the reference points in the objective space. Computational experiments are performed on a bi-objective flow-shop scheduling problem. Results, quality measures as well as a statistical analysis are reported in the paper.     

A Reference Direction Algorithm for Solving Multiple Objective Integer Linear Programming Problems

In this paper, we propose a reference direction approach and an interactive algorithm to solve the general multiple objective integer linear programming problem. At each iteration, only one mixed integer linear programming problem is solved to find an (weak) efficient solution. Each intermediate solution is integer. The decision maker has to provide only the reference point at each iteration. No special software is required to implement the proposed algorithm. The algorithm is illustrated with an example.     

Cone contraction and reference point methods for multi-criteria mixed integer optimization

Interactive approaches employing cone contraction for multi-criteria mixed integer optimization are introduced. In each iteration, the decision maker (DM) is asked to give a reference point (new aspiration levels). The subsequent Pareto optimal point is the reference point projected on the set of admissible objective vectors using a suitable scalarizing function. Thereby, the procedures solve a sequence of optimization problems with integer variables. In such a process, the DM provides additional preference information via pair-wise comparisons of Pareto optimal points identified. Using such preference information and assuming a quasiconcave and non-decreasing value function of the DM we restrict the set of admissible objective vectors by excluding subsets, which cannot improve over the solutions already found. The procedures terminate if all Pareto optimal solutions have been either generated or excluded. In this case, the best Pareto point found is an optimal solution. Such convergence is expected in the special case of pure integer optimization; indeed, numerical simulation tests with multi-criteria facility location models and knapsack problems indicate reasonably fast convergence, in particular, under a linear value function. We also propose a procedure to test whether or not a solution is a supported Pareto point (optimal under some linear value function).     

Lower Semicontinuity Results in Parametric Multivalued Weak Vector Equilibrium Problems and Applications

This article gives new sufficient conditions for the lower semicontinuity of the solution mapping of a parametric multivalued weak vector equilibrium problem with moving cones. A scalarizing approach, based on the signed distance function of Hiriart Urruty is used to discuss this lower semicontinuity property. The main results of the article are obtained under some assumptions different from those introduced earlier by previous linear and nonlinear scalarizing approaches. Some applications to the study of connectedness of weak solution sets of multivalued vector equilibrium problems are given.     

An interactive solution approach for a bi-objective semi-desirable location problem

In this study, we consider a semi-desirable facility location problem in a continuous planar region considering the interaction between the facility and the existing demand points. A facility can be defined as semi-desirable if it has both undesirable and desirable effects to the people living in the vicinity. Our aim is to maximize the weighted distance of the facility from the closest demand point as well as to minimize the service cost of the facility. The distance between the facility and the demand points is measured with the rectilinear metric. For the solution of the problem, a three-phase interactive geometrical branch and bound algorithm is suggested to find the most preferred efficient solution. In the first two phases, we aim to eliminate the parts of the feasible region the inefficiency of which can be proved. The third phase has been suggested for an interactive search in the remaining regions with the involvement of a decision maker (DM). In the third phase, the DM is given the opportunity to use either an exact or an approximate procedure to carry out the search. The exact procedure is based on the reference point approach and guarantees to find an efficient point as the most preferred solution. On the other hand, in the approximate procedure, a hybrid methodology is used to increase the efficiency of the reference point approach. The approximate procedure can be used when the DM prefers to see locally efficient solutions so as to save computation time. We demonstrate the performance of the proposed method through example problems.     

Use of Substitute Scalarizing Functions to Guide a Local Search Based Heuristic: The Case of moTSP

Solving the Tchebycheff program means optimizing a particular scalarizing function. When dealing with combinatorial problems, however, it is due to computational intractability often necessary to apply heuristics and settle for approximations to the optimal solution. The experiments in this paper suggest that for the multiobjective traveling salesman problem (moTSP) instances considered, heuristic optimization of the Tchebycheff program gives better results when using a substitute scalarizing function instead of the Tchebycheff based one to guide the local search path. Two families of substitute scalarizing functions are considered.     

An efficient hybrid numerical method based on an additive scheme for solving coupled systems of singularly perturbed linear parabolic problems

We construct an efficient hybrid numerical method for solving coupled systems of singularly perturbed linear parabolic problems of reaction-diffusion type. The discretization of the coupled system is based on the use of an additive or splitting scheme on a uniform mesh in time and a hybrid scheme on a layer-adapted mesh in space. It is proven that the developed numerical method is uniformly convergent of first order in time and third order in space. The purpose of the additive scheme is to decouple the components of the vector approximate solution at each time step and thus make the computation more efficient. The numerical results confirm the theoretical convergence result and illustrate the efficiency of the proposed strategy.     

Gradient projection and local region search for multiobjective optimisation

This paper presents a new method for multiobjective optimisation based on gradient projection and local region search. The gradient projection is conducted through the identification of normal vectors of an efficient frontier. The projection of the gradient of a nonlinear utility function onto the tangent plane of the efficient frontier at a given efficient solution leads to the definition of a feasible local region in a neighbourhood of the solution. Within this local region, a better efficient solution may be sought. To implement such a gradient-based local region search scheme, a new auxiliary problem is developed. If the utility function is given explicitly, this search scheme results in an iterative optimisation algorithm capable of general nonseparable multiobjective optimisation. Otherwise, an interactive decision making algorithm is developed where the decision maker (DM) is expected to provide local preference information in order to determine trade-off directions and step sizes. Optimality conditions for the algorithms are established and the convergence of the algorithms is proven. A multiobjective linear programming (MOLP) problem is taken for example to demonstrate this method both graphically and analytically. A nonlinear multiobjective water quality management problem is finally examined to show the potential application of the method to real world decision problems.     

Nonlinear scalarizing functions in set optimization problems

In this paper, we obtain Hölder continuity of the nonlinear scalarizing function for l-type less order relation, which is introduced by Hernández and Rodríguez-Marín (J. Math. Anal. Appl. 2007;325:1–18). Moreover, we introduce the nonlinear scalarizing function for u-type less order relation and establish continuity, convexity and Hölder continuity of the nonlinear scalarizing function for u-type less order relation. As applications, we firstly obtain Lipschitz continuity of solution mapping to the parametric equilibrium problems and then establish Lipschitz continuity of strongly approximate solution mappings for l-type less order relation, u-type less order relation and set less order relation to the parametric set optimization problems by using convexity and Hölder continuity of the nonlinear scalarizing functions.     

Continuity and Convexity of a Nonlinear Scalarizing Function in Set Optimization Problems with Applications

Hern\(\acute{\mathrm{a}}\)ndez and Rodríguez-Marín (J Math Anal Appl 325:1–18, 2007) introduced a nonlinear scalarizing function for sets, which is a generalization of the Gerstewitz’s function. This paper aims at investigating some properties concerned with the nonlinear scalarizing function for sets. The continuity and convexity of the nonlinear scalarizing function for sets are showed under some suitable conditions. As applications, the upper semicontinuity and the lower semicontinuity of strongly approximate solution mappings to the parametric set optimization problems are also given.