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.     

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.     

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.     

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.     

A mathematical basis for satisficing decision making

This paper presents a conceptual and mathematical model of the process of satisficing decision making under multiple objectives in which the information about decision maker's preferences is expressed in the form of aspiration levels. The mathematical concept of a value (utility) function is modified to describe satisficing behavior; the modified value function (achievement scalarizing function) should possess the properties of order preservation and order approximation. It is shown that the mathematical basis formed using aspiration levels and achievement scalarizing functions can be used not only for satisficing decision making but also for Pareto optimization, and thus provides an alternative to approaches based on weighting coefficients or typical value functions. This mathematical basis, which can also be regarded as a generalization of the goal programming approach in multiobjective optimization, suggests pragmatic approaches to many problems in multiobjective analysis.     

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.     

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.     

Saddle points and scalarizing sets in multiple objective linear programming

The main purpose of this paper is to study saddle points of the vector Lagrangian function associated with a multiple objective linear programming problem. We introduce three concepts of saddle points and establish their characterizations by solving suitable systems of equalities and inequalities. We deduce dual programs and prove a relationship between saddle points and dual solutions, which enables us to obtain an explicit expression of the scalarizing set of a given saddle point in terms of normal vectors to the value set of the problem. Finally, we present an algorithm to compute saddle points associated with non-degenerate vertices and the corresponding scalarizing sets.     

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.     

Four types of nonlinear scalarizations and some applications in set optimization

There are two types of criteria of solutions for the set-valued optimization problem, the vectorial criterion and set optimization criterion. The first criterion consists of looking for efficient points of set valued map and is called set-valued vector optimization problem. On the other hand, Kuroiwa–Tanaka–Ha started developing a new approach to set-valued optimization which is based on comparison among values of the set-valued map. In this paper, we treat the second type criterion and call set optimization problem. The aim of this paper is to investigate four types of nonlinear scalarizing functions for set valued maps and their relationships. These scalarizing functions are generalization of Tammer–Weidner’s scalarizing functions for vectors. As applications of the scalarizing functions for sets, we present nonconvex separation type theorems, Gordan’s type alternative theorems for set-valued map, optimality conditions for set optimization problem and Takahashi’s minimization theorems for set-valued map.     

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.     

Experiments with classification-based scalarizing functions in interactive multiobjective optimization

In multiobjective optimization methods, the multiple conflicting objectives are typically converted into a single objective optimization problem with the help of scalarizing functions and such functions may be constructed in many ways. We compare both theoretically and numerically the performance of three classification-based scalarizing functions and pay attention to how well they obey the classification information. In particular, we devote special interest to the differences the scalarizing functions have in the computational cost of guaranteeing Pareto optimality. It turns out that scalarizing functions with or without so-called augmentation terms have significant differences in this respect. We also collect a set of mostly nonlinear benchmark test problems that we use in the numerical comparisons.     

An improved algorithm for solving biobjective integer programs

A parametric algorithm for identifying the Pareto set of a biobjective integer program is proposed. The algorithm is based on the weighted Chebyshev (Tchebycheff) scalarization, and its running time is asymptotically optimal. A number of extensions are described, including: a technique for handling weakly dominated outcomes, a Pareto set approximation scheme, and an interactive version that provides access to all Pareto outcomes. Extensive computational tests on instances of the biobjective knapsack problem and a capacitated network routing problem are presented.     

Gap functions for vector variational inequalities

In this article, we intend to study several scalar-valued gap functions for Stampacchia and Minty-type vector variational inequalities. We first introduce gap functions based on a scalarization technique and then develop a gap function without any scalarizing parameter. We then develop its regularized version and under mild conditions develop an error bound for vector variational inequalities with strongly monotone data. Further, we introduce the notion of a partial gap function which satisfies all, but one of the properties of the usual gap function. However, the partial gap function is convex and we provide upper and lower estimates of its directional derivative.     

A unified vector optimization problem: complete scalarizations and applications

The aim of this article is to introduce and analyse a general vector optimization problem in a unified framework. Using a well-known nonlinear scalarizing function defined by a solid set, we present complete scalarizations of the solution set to the vector problem without any convexity assumptions. As applications of our results we obtain new optimality conditions for several classical optimization problems by characterizing their solution set.     

New Results on Henig Proper Generalized Vector Quasiequilibrium Problems

New sufficient conditions are given for the existence of solutions of a Henig proper generalized vector quasiequilibrium problem with moving cones. They are established by a new scalarizing approach, which is based on a suitable nonlinear scalarization function, proposed recently for set-valued maps in Sach and Tuan (J. Optim. Theory Appl. 157:347–364 (2013)). Examples are given to illustrate our main results.     

A characterization of Tchebycheff systems

A characterization of Tchebycheff systems is given, in terms of Weak Tchebycheff systems.     

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.     

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.     

Functions of bounded variation with respect to a Tchebycheff system

A characterization of Tchebycheff systems is given, in terms of Weak Tchebycheff systems.