Stability of nondominated solutions in multicriteria decision-making

Decision-making problems with multiple noncommensurable objectives are specified by two factors, i.e., the set of all feasible solutions and the domination structure. The solutions are characterized as nondominated points. Hence, in these problems, there may exist two parameter vectors, according to which the above two factors change. The stability of the solution set for perturbations of these parameters is investigated in this paper. The analysis is guided by using the concept of continuity of the solution map defined on the two parameter spaces.     

Necessary conditions of nondominated solutions in multicriteria decision making

A partial integrodifferential equation is studied in which the derivatives of highest order also contain a discrete and a distributed delay. By means of abstract regularity results, global existence and uniqueness of a strict solution are obtained; moreover a characterization of the infinitesimal generator of the solution operator is given.     

Connectedness of the set of nondominated outcomes in multicriteria optimization

Sufficient conditions for the set of nondominated outcomes of a multicriteria optimization problem to be connected are given.The author would like to thank Professors G. Leitmann and P. L. Yu for many critical remarks.The contents of this article are taken from the author's doctoral dissertation written at the University of California at Berkeley under the supervision of Professor G. Leitmann.     

Generalization of domination structures and nondominated solutions in multicriteria decision making

The concepts of domination structures and nondominated solutions are important in tackling multicriteria decision problems. We relax Yu's requirement that the domination structure at each point of the criteria space be a convex cone (Ref. 1) and give results concerning the set of nondominated solutions for the case where the domination structure at each point is a convex set. A practical necessity for such a generalization is discussed. We also present conditions under which a locally nondominated solution is also a globally nondominated solution.     

An approximate solution of linear multicriteria control problems through the multicriteria simplex method

This paper deals with multicriteria, linear, continuous optimal control problems through the application of the multicriteria simplex method. Since the system is linear, the state variables at a given time can be expressed in terms of definite integrals. Upon using standard numerical integration formulas, the definite integrals are approximately expressed by means of weighted sums of the integrands. Then, after introducing some suitable auxiliary variables, approximate linear multicriteria programming problems are formulated. Illustrative numerical examples are provided to indicate the efficiency of the proposed method.The author is indebted to Professor Y. Sawaragi of Kyoto University for his constant encouragement. The author also wishes to thank T. Suwa for his cooperation in preparing the programming for the digital computer.     

A general method for determining the set of all efficient solutions to a linear vectormaximum problem

To solve a linear vectormaximum problem means, in general, to determine the set E of all efficient solutions. A multiparametric method based on earlier works of the author is presented. In the procedure efficient vertices and efficient edges are generated via one subprogram, which works as a simple linear programming problem, and just by inspection of these results higher dimensional efficient faces are determined. The procedure does not depend on special properties of the restriction set and/or of the system of given objective functions. Illustrative examples are presented. Two appendixes provide a survey on a multiparametric algorithm and on a solution procedure for the auxiliary problem, both of which are the background for the method.     

A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems

Most real-life decision-making activities require more than one objective to be considered. Therefore, several studies have been presented in the literature that use multiple objectives in decision models. In a mathematical programming context, the majority of these studies deal with two objective functions known as bicriteria optimization, while few of them consider more than two objective functions. In this study, a new algorithm is proposed to generate all nondominated solutions for multiobjective discrete optimization problems with any number of objective functions. In this algorithm, the search is managed over (p − 1)-dimensional rectangles where p represents the number of objectives in the problem and for each rectangle two-stage optimization problems are solved. The algorithm is motivated by the well-known ε-constraint scalarization and its contribution lies in the way rectangles are defined and tracked. The algorithm is compared with former studies on multiobjective knapsack and multiobjective assignment problem instances. The method is highly competitive in terms of solution time and the number of optimization models solved.     

Quasiconcavity and nondominated solutions in multiobjective programming

In the multiobjective programming literature, the concavity of the objectives is usually assumed to be a sufficient condition in seeking Pareto-optimal solutions. This paper investigates nondominated solutions associated with dominance cones via the assumption of the quasiconcavity of the objectives. Necessary as well as sufficient conditions for such quasiconcave multiobjective programming problems are obtained.The author is indebted to one of the referees for detailed constructive comments and suggestions. Thanks are also due to the late Professor Abraham Charnes, University of Texas at Austin, and Professor Zhimin Huang, Adelphi University.     

Assessing a set of additive utility functions for multicriteria decision-making,the UTA method

The purpose of the method presented in this paper is to assess additive utility functions which aggregate multiple criteria in a composite criterion, using the information given by a subjective ranking on a set of stimuli or actions (weak-order comparison judgments) and the multicriteria evaluations of these actions. It is an ordinal regression method using linear programming to estimate the parameters of the utility function.Stability and sensitivity analysis leads to the assessment of a set of utility functions by means of post-optimality analysis techniques in linear programming.Finally, a simple illustrative example is presented and some extensions of the method are proposed.     

On the simplex method and a class of linear complementary problems

We consider the linear complementarity problem of finding vectors w?Rⁿ, z?Rⁿ satisfying w ? Mz = q, w ? 0, z ? 0, w^Tz = 0. We show that if the off diagonal elements of M are nonpositive, then the above problem is solved by applying the simplex method to the problem Minimize z₀ subject to w ? Mz ? e_nz₀ = q, (z₀, w, z) ? 0, where e_n is a column vector of 1's. In fact the sequence of basic feasible solutions obtained by the simplex method and by Lemke's algorithm are the same. We also obtain necessary and sufficient conditions for the problem to have solutions for all q.     

Optimization of a linear function over the set of stochastic efficient solutions

In this paper we study the problem of optimization over an integer efficient set of a Multiple Objective Integer Linear Stochastic Programming problem. Once the problem is converted into a deterministic one by adapting the $2$ -levels recourse approach, a new pivoting technique is applied to generate an optimal efficient solution without having to enumerate all of them. This method combines both techniques, the L-shaped method and the combined method developed in Chaabane and Pirlot (J Ind Manag Optim 6:811–823, 2010). A detailed didactic example is given to illustrate different steps of our algorithm.     

Computing all solutions of linear generalized Nash equilibrium problems

In this paper we consider linear generalized Nash equilibrium problems, i.e., the cost and the constraint functions of all players in a game are assumed to be linear. Exploiting duality theory, we design an algorithm that is able to compute the entire solution set of these problems and that terminates after finite time. We present numerical results on some academic examples as well as some economic market models to show effectiveness of our algorithm in small dimensions.     

Characterization of nondominated controls in terms of solutions of weighting problems

The problem of continuously dynamic multiobjective optimization, or multiobjective control, is discussed. The concepts of nondominated controls and viable controls are introduced. For a class of nonlinear dynamic systems, the convexity of their controlled Carathéodory trajectories is proved. Based on this convexity, sufficient conditions are given for the solution of a multiobjective control problem to be obtained in terms of solutions of weighting problems.This work was partly done at the Huazhong University of Science and Technology, Wuhan, China. The author is indebted to Professor Chen Ting for his advice. The author wishes to thank Professor G. Leitmann for his favorable comments. The author is also grateful to Ms. Mary S. Linn at the University of Kansas, who helped him improve the English presentation of this paper.     

Application of the ellipsoid method in an interactive procedure for multicriteria linear programming

The research reported in this paper is concerned with an application of the ellipsoid algorithm in the interactive multicriteria linear programming step method (STEM) byBenayoun et al. [1971]. Due to this application we eliminate some drawbacks of the original version of STEM and, moreover, we avoid extra computations connected with sensitivity analysis in every iteration. Specifically, we use the ellipsoid algorithm to minimize the Euclidean norm in the criterion space instead of the Chebyshev norm, which ensures that every solution submitted to the decision maker is efficient. As follows from a computational experiment, in comparison with the application of the simplex method, the proposed modification of STEM shows a smaller increase of the computational effort when the number of criteria increases. However, the absolute computation time becomes worse for problems of larger size.

---

Zusammenfassung In dieser Arbeit wird über eine Anwendungsmöglichkeit der Khachiyan-Shor-Algorithmus (Ellipsoid-Algorithmus) im Rahmen des STEM-Verfahrens zur interaktiven Lösung linearer Vektoroptimierungsmodelle berichtet. Auf diese Weise können einige spezifische Nachteile des STEM-Verfahrens in seiner Originalversion vermieden werden. Durch die Verwendung der Euklidischen Norm anstelle der beim STEM-Verfahren üblichen Tschebyscheff-Norm wird garantiert, daß dem Entscheidungsträger nur effiziente Lösungen vorgeschlagen werden. Die numerischen Erfahrungen zeigen, daß der Lösungsaufwand der hier vorgeschlagenen Modifikation des STEM-Verfahrens mit steigender Anzahl von Zielfunktionen weniger stark zunimmt als bei der üblichen Version. Dies gilt jedoch nicht hinsichtlich der allgemeinen Problemgröße.

     

Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem

This paper deals with the LCP (linear complementarity problem) with a positive semi-definite matrix. Assuming that a strictly positive feasible solution of the LCP is available, we propose ellipsoids each of which contains all the solutions of the LCP. We use such an ellipsoid for computing a lower bound and an upper bound for each coordinate of the solutions of the LCP. We can apply the lower bound to test whether a given variable is positive over the solution set of the LCP. That is, if the lower bound is positive, we know that the variable is positive over the solution set of the LCP; hence, by the complementarity condition, its complement is zero. In this case we can eliminate the variable and its complement from the LCP. We also show how we efficiently combine the ellipsoid method for computing bounds for the solution set with the path-following algorithm proposed by the authors for the LCP. If the LCP has a unique non-degenerate solution, the lower bound and the upper bound for the solution, computed at each iteration of the path-following algorithm, both converge to the solution of the LCP.Supported by Grant-in-Aids for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Young Scientists (63730014) and for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.