A review of interactive methods for multiobjective integer and mixed-integer programming

This paper makes a review of interactive methods devoted to multiobjective integer and mixed-integer programming (MOIP/MOMIP) problems. The basic concepts concerning the characterization of the non-dominated solution set are first introduced, followed by a remark about non-interactive methods vs. interactive methods. Then, we focus on interactive MOIP/MOMIP methods, including their characterization according to the type of preference information required from the decision maker, the computing process used to determine non-dominated solutions and the interactive protocol used to communicate with the decision maker. We try to draw out some contrasts and similarities of the different types of methods.     

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.     

Using box indices in supporting comparison in multiobjective optimization

Because of the conflicting nature of criteria or objectives, solving a multiobjective optimization problem typically requires interaction with a decision maker who can specify preference information related to the objectives in the problem in question. Due to the difficulties of dealing with multiple objectives, the way information is presented plays a very important role. Questions posed to the decision maker must be simple enough and information shown must be easy to understand. For this purpose, visualization and graphical representations can be useful and constitute one of the main tools used in the literature. In this paper, we propose to use box indices to represent information related to different solution alternatives of multiobjective optimization problems involving at least three objectives. Box indices are an intelligible and easy to handle way to represent data. They are based on evaluating the solutions in a natural and rough enough scale in order to let the decision maker easily recognize the main characteristics of a solution at a glance and to facilitate comparison of two or more solutions in an easily understandable way.     

An additive achievement scalarizing function for multiobjective programming problems

The success of the reference point scheme within interactive techniques for multiobjective programming problems is unquestionable. However, so far, the different achievement scalarizing functions are, more or less, extensions of the Tchebychev distance. The reason for this is the ability of this function to determine efficient solutions and to support every efficient solution of the problem. For the same reasons, no additive scheme has yet been used in reference point-based interactive methods. In this paper, an additive achievement scalarizing function is proposed. Theoretical results prove that this function supports every efficient solution, and conditions are given under which the efficiency of each solution is guaranteed. Some examples and computational tests show the different behaviours of the Tchebychev and additive approaches, and an additive reference point interactive algorithm is proposed.     

An interactive satisficing method based on alternative tolerance for fuzzy multiple objective optimization

An interactive satisficing method based on alternative tolerance is proposed for fuzzy multiple objective optimization. The new tolerances of the dissatisficing objectives are generated using an auxiliary programming problem. According to the alternative tolerant limits, either the membership functions are changed, or the objective constraints are added. The lexicographic two-phase programming is implemented to find the final solution. The results of the dissatisficing objectives are iteratively improved. The presented method not only acquires the efficient or weak efficient solution of all the objectives, but also satisfies the progressive preference of decision maker. Numerical examples show its power.     

ISTMO: An interval reference point-based method for stochastic multiobjective programming problems

In this paper, we present an interactive algorithm (ISTMO) for stochastic multiobjective problems with continuous random variables. This method combines the concept of probability efficiency for stochastic problems with the reference point philosophy for deterministic multiobjective problems. The decision maker expresses her/his references by dividing the variation range of each objective into intervals, and by setting the desired probability for each objective to achieve values belonging to each interval. These intervals may also be redefined during the process. This interactive procedure helps the decision maker to understand the stochastic nature of the problem, to discover the risk level (s)he is willing to assume for each objective, and to learn about the trade-offs among the objectives.     

Tradeoff directions in multiobjective optimization problems

Multiobjective optimization problems (MOP) typically have conflicting objectives wherein a gain in one objective is at the expense of another. Tradeoff directions, which measure the change in some objectives relative to changes in others, provide important information as to the best direction of improvement from the current solution. In this paper we present a general definition of tradeoffs as a cone of directions and provide a general method of calculating tradeoffs at every Pareto optimal point of a convex MOP. This extends current definitions of tradeoffs which assume certain conditions on the feasible set and the objective functions. Two comprehensive numerical examples are provided to illustrate the tradeoff directions and the methods used to calculate them.     

An iterative approach to solve multiobjective linear fractional programming problems

This paper suggests an iterative parametric approach for solving multiobjective linear fractional programming (MOLFP) problems which only uses linear programming to obtain efficient solutions and always converges to an efficient solution. A numerical example shows that this approach performs better than some existing algorithms. Randomly generated MOLFP problems are also solved to demonstrate the performance of new introduced algorithm.     

A multiplicative version of Promethee II applied to multiobjective optimization problems

The method Promethee II has produced attractive results in the choice of the most satisfactory optimal solution of convex multiobjective problems. However, according to the current literature, it may not work properly with nonconvex problems. A modified version of this method, called multiplicative Promethee, is proposed in this paper. Both versions are applied to some analytical problems, previously optimized by an evolutionary algorithm. The multiplicative Promethee got much better results than the original Promethee II, being capable of solving convex and nonconvex problems, with continuous and discontinuous Pareto fronts.     

A novel elitist multiobjective optimization algorithm: Multiobjective extremal optimization

Recently, a general-purpose local-search heuristic method called extremal optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in numerical multiobjective optimization and proposes a new novel elitist (1 + λ) multiobjective algorithm, called multiobjective extremal optimization (MOEO). In order to extend EO to solve the multiobjective optimization problems, the Pareto dominance strategy is introduced to the fitness assignment of the proposed approach. We also present a new hybrid mutation operator that enhances the exploratory capabilities of our algorithm. The proposed approach is validated using five popular benchmark functions. The simulation results indicate that the proposed approach is highly competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOEO can be considered a good alternative to solve numerical multiobjective optimization problems.     

A necessary and sufficient condition for duality in multiobjective variational problems

In this paper we move forward in the study of duality and efficiency in multiobjective variational problems. We introduce new classes of pseudoinvex functions, and prove that not only it is a sufficient condition to establish duality results, but it is also necessary. Moreover, these functions are characterized in order that all Kuhn–Tucker or Fritz John points are efficient solutions. Recent papers are improved. We provide an example to show this improvement and illustrate these classes of functions and results.     

An alternative optimization technique for interval objective constrained optimization problems via multiobjective programming

An alternative optimization technique via multiobjective programming for constrained optimization problems with interval-valued objectives has been proposed. Reduction of interval objective functions to those of noninterval (crisp) one is the main ingredient of the proposed technique. At first, the significance of interval-valued objective functions along with the meaning of interval-valued solutions of the proposed problem has been explained graphically. Generally, the proposed problems have infinitely many compromise solutions. The objective is to obtain one of such solutions with higher accuracy and lower computational effort. Adequate number of numerical examples has been solved in support of this technique.     

A hybrid immune multiobjective optimization algorithm

In this paper, we develop a hybrid immune multiobjective optimization algorithm (HIMO) based on clonal selection principle. In HIMO, a hybrid mutation operator is proposed with the combination of Gaussian and polynomial mutations (GP-HM operator). The GP-HM operator adopts an adaptive switching parameter to control the mutation process, which uses relative large steps in high probability for boundary individuals and less-crowded individuals. With the generation running, the probability to perform relative large steps is reduced gradually. By this means, the exploratory capabilities are enhanced by keeping a desirable balance between global search and local search, so as to accelerate the convergence speed to the true Pareto-optimal front in the global space with many local Pareto-optimal fronts. When comparing HIMO with various state-of-the-art multiobjective optimization algorithms developed recently, simulation results show that HIMO performs better evidently.     

An empirical study on similarity-based mating for evolutionary multiobjective combinatorial optimization

We have already proposed a similarity-based mating scheme to recombine extreme and similar parents for evolutionary multiobjective optimization. In this paper, we examine the effect of the similarity-based mating scheme on the performance of evolutionary multiobjective optimization (EMO) algorithms. First we examine which is better between recombining similar or dissimilar parents. Next we examine the effect of biasing selection probabilities toward extreme solutions that are dissimilar from other solutions in each population. Then we examine the effect of dynamically changing the strength of this bias during the execution of EMO algorithms. Computational experiments are performed on a wide variety of test problems for multiobjective combinatorial optimization. Experimental results show that the performance of EMO algorithms can be improved by the similarity-based mating scheme for many test problems.     

Asymptotic convergence of a simulated annealing algorithm for multiobjective optimization problems

In this paper we consider a simulated annealing algorithm for multiobjective optimization problems. With a suitable choice of the acceptance probabilities, the algorithm is shown to converge asymptotically, that is, the Markov chain that describes the algorithm converges with probability one to the Pareto optimal set.     

An exact penalty on bilevel programs with linear vector optimization lower level

We are interested in a class of linear bilevel programs where the upper level is a linear scalar optimization problem and the lower level is a linear multi-objective optimization problem. We approach this problem via an exact penalty method. Then, we propose an algorithm illustrated by numerical examples.     

Target setting in the general combined-oriented CCR model using an interactive MOLP method

The traditional data envelopment analysis (DEA) model does not include a decision maker’s (DM) preference structure while measuring relative efficiency, with no or minimal input from the DM. To incorporate DM’s preference information in DEA, various techniques have been proposed. An interesting method to incorporate preference information, without necessary prior judgment, is the use of an interactive decision making technique that encompasses both DEA and multi-objective linear programming (MOLP). In this paper, we will use Zionts-Wallenius (Z-W) method to reflecting the DM’s preferences in the process of assessing efficiency in the general combined-oriented CCR model. A case study will conducted to illustrate how combined-oriented efficiency analysis can be conducted using the MOLP method.     

InterQuad: An interactive quad tree based procedure for solving the discrete alternative multiple criteria problem

In this paper an interactive procedure based upon a data structure called a quad tree is developed for solving the discrete alternative multiple criteria problem. Called InterQuad, the procedure has been designed with large discrete alternative problems in mind. InterQuad takes advantage of the ability of a quad tree to identify, store, and retrieve nondominated criterion vectors. Then, the user interacts with the nondominated criterion vectors stored in the quad tree in a fashion similar to that of the Combined Tchebycheff/Aspiration Criterion Vector Procedure of Steuer, Silverman and Whisman.     

Robust optimization for interactive multiobjective programming with imprecise information applied to R&D project portfolio selection

A multiobjective binary integer programming model for R&D project portfolio selection with competing objectives is developed when problem coefficients in both objective functions and constraints are uncertain. Robust optimization is used in dealing with uncertainty while an interactive procedure is used in making tradeoffs among the multiple objectives. Robust nondominated solutions are generated by solving the linearized counterpart of the robust augmented weighted Tchebycheff programs. A decision maker’s most preferred solution is identified in the interactive robust weighted Tchebycheff procedure by progressively eliciting and incorporating the decision maker’s preference information into the solution process. An example is presented to illustrate the solution approach and performance. The developed approach can also be applied to general multiobjective mixed integer programming problems.     

An interactive dynamic approach based on hybrid swarm optimization for solving multiobjective programming problem with fuzzy parameters

Real engineering design problems are generally characterized by the presence of many often conflicting and incommensurable objectives. Naturally, these objectives involve many parameters whose possible values may be assigned by the experts. The aim of this paper is to introduce a hybrid approach combining three optimization techniques, dynamic programming (DP), genetic algorithms and particle swarm optimization (PSO). Our approach integrates the merits of both DP and artificial optimization techniques and it has two characteristic features. Firstly, the proposed algorithm converts fuzzy multiobjective optimization problem to a sequence of a crisp nonlinear programming problems. Secondly, the proposed algorithm uses H-SOA for solving nonlinear programming problem. In which, any complex problem under certain structure can be solved and there is no need for the existence of some properties rather than traditional methods that need some features of the problem such as differentiability and continuity. Finally, with different degree of α we get different α-Pareto optimal solution of the problem. A numerical example is given to illustrate the results developed in this paper.