The set of all nondominated solutions in linear cases and a multicriteria simplex method

In this note we are interested in the properties of, and methods for locating the set of all nondominated solutions of multiple linear criteria defined over a polyhedron. We first show that the set of all dominated solutions is convex and that the set of all nondominated solutions is a subset of the convex hull of the nondominated extreme points. When the domination cone is polyhedral, we derive a necessary and sufficient condition for a point to be nondominated. The condition is stronger than that of Ref. [1] and enables us to give a simple proof that the set of all nondominated extreme points indeed is connected. In order to locate the entire set of all nondominated extreme points, we derive a generalized version of simplex method—multicriteria simplex method. In addition to some useful results, a necessary and sufficient condition for an extreme point to be nondominated is derived. Examples and computer experience are also given. Finally, we focus on how to generate the entire set of all nondominated solutions through the set of all nondominated extreme points. A decomposition theorem and some necessary and sufficient conditions for a face to be nondominated are derived. We then describe a systematic way to identify the entire set of all nondominated solutions. Through examples, we show that in fact our procedure is quite efficient.     

Multiple criteria decision problems with fuzzy domination structures

The concepts of domination structures and nondominated solutions in multiple criteria decision problems, which were introduced by Yu, enable us to tackle general situations in which there exists information concerning the decision maker's preferences.In many of the multiple criteria decision problems the underlying domination structures are not known precisely but only fuzzily determined. Yu primarily works with the case where the domination structure at each point is a convex cone. As a result, there exists a sharp borderline dividing all solutions into nondominated solutions and the others.This paper fuzzifies the concepts of domination structures and nondominated solutions to allow them to be applied to a larger class of the multiple criteria decision problems mentioned above. Introducing the concepts of fuzzy convex cones and fuzzy polar cones, it is shown how some of the main results obtained by Yu are extended.     

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.     

Norm-Based Approximation in Bicriteria Programming

An algorithm to approximate the nondominated set of continuous and discrete bicriteria programs is proposed. The algorithm employs block norms to find an approximation and evaluate its quality. By automatically adapting to the problem's structure and scaling, the approximation is constructed objectively without interaction with the decision maker. Mathematical and practical examples are included.     

Potential solutions of linear systems: The multi-criteria multiple constraint levels program

The realistic modeling of decision problems requires considerable flexibility in the model structure. Frequently one is faced with problems involving multiple criteria for which the constraint level is acceptable if a certain parameter (which may be a random variable) lies within a prescribed set. Furthermore, in formulating the problem, the criteria and constraints may be interchangeable. This requires a treatment which is more general than the nondominated solution in a multicriteria problem. We shall introduce the concept of a potential solution to cope with the above problem. To effectively locate these potential solutions, a generalization of the multicriteria (MC) simplex method, which handles multiple constraint levels (right hand sides) is developed. Geometric properties of adjacent potential solutions will be described together with a computational procedure which is based on the “connectedness” of the set of potential solutions. The natural duality relationship which exists in the double-MC simplex method and its consequences are also explored.     

Nondominated Equilibrium Solutions of a Multiobjective Two-Person Nonzero-Sum Game and Corresponding Mathematical Programming Problem

With reference to a multiobjective two-person nonzero-sum game, we define nondominated equilibrium solutions and provide a necessary and sufficient condition for a pair of mixed strategies to be a nondominated equilibrium solution. Using the necessary and sufficient condition, we formulate a mathematical programming problem yielding nondominated equilibrium solutions. We give a numerical example and demonstrate that nondominated equilibrium solutions can be obtained by solving the formulated mathematical programming problem.     

Suitable-portfolio investors,nondominated frontier sensitivity,and the effect of multiple objectives on standard portfolio selection

In standard portfolio theory, an investor is typically taken as having one stochastic objective, to maximize the random variable of portfolio return. But in this paper, we focus on investors whose purpose is to build, more broadly, a “suitable portfolio” taking additional concerns into account. Such investors would have additional stochastic and deterministic objectives that might include liquidity, dividends, number of securities in a portfolio, social responsibility, and so forth. To accommodate such investors, we develop a multiple criteria portfolio selection formulation, corroborate its appropriateness by examining the sensitivity of the nondominated frontier to various factors, and observe the conversion of the nondominated frontier to a nondominated surface. Furthermore, multiple criteria enable us to provide an explanation as to why the “market portfolio,” so often found deep below the nondominated frontier, is roughly where one would expect it to be with multiple criteria. After commenting on solvability issues, the paper concludes with the idea that what is the “modern portfolio theory” of today might well be interpreted as a projection onto two-space of a real multiple criteria portfolio selection problem from higher dimensional space. M. Hirschberger: Research conducted while a Visiting Scholar at the Department of Banking and Finance, Terry College of Business, University of Georgia, October 2003–March 2004.     

Cone convexity,cone extreme points,and nondominated solutions in decision problems with multiobjectives

Although there is no universally accepted solution concept for decision problems with multiple noncommensurable objectives, one would agree that agood solution must not be dominated by the other feasible alternatives. Here, we propose a structure of domination over the objective space and explore the geometry of the set of all nondominated solutions. Two methods for locating the set of all nondominated solutions through ordinary mathematical programming are introduced. In order to achieve our main results, we have introduced the new concepts of cone convexity and cone extreme point, and we have explored their main properties. Some relevant results on polar cones and polyhedral cones are also derived. Throughout the paper, we also pay attention to an important special case of nondominated solutions, that is, Pareto-optimal solutions. The geometry of the set of all Pareto solutions and methods for locating it are also studied. At the end, we provide an example to show how we can locate the set of all nondominated solutions through a derived decomposition theorem.     

Generalized Maximin Solutions in Multicriteria Bargaining

In this paper we address bargaining games where the agents have to take into account different criteria to value the decisions. We propose the class of generalized maximin solutions, as the natural extension for these games of the maximin solutions in conventional bargaining. In order to refine this solution concept, we define a multicriteria lexicographic partial ordering and present the class of generalized leximin solutions as those that are nondominated with respect to this relation. We establish some properties of these solutions and characterize them as solutions of multicriteria problems. The research of the authors is partially supported by the Spanish Ministry of Science and Technology projects BFM2002-11282-E and BEC2003-03111.     

Characterizing the nondominated set by separable functions

We present sufficient and necessary conditions for classes of separable (additive) functions to generate the set of nondominated outcomes in multicriteria optimization problems. The basic technique consists of convexifying the set of outcomes and then applying the standard characterization of a convex set by a class of linear functions. The conditions include the case when the set of feasible alternatives is convex and the criteria are convex-transformable. We show that the sum of powers and the sum of functions of exponents can generate the nondominated set for an arbitrary set of outcomes (under compactness conditions). We also discuss monotonicity, proper nondominance, uniqueness and connectedness of solutions, and weights and trade-offs with respect to these functions.The research was done while the author was Visiting Professor at the University of Illinois at Urbana-Champaign, Illinois. The author is grateful to G. Hazen, Northwestern University, for helpful discussions.     

A reference direction approach to multiple objective quadratic-linear programming

In this paper, we propose an interactive procedure for solving multiple criteria problems with one quadratic objective, several linear objectives, and a set of linear constraints. The procedure is based on the use of reference directions and weighted sums. Reference directions for the linear functions, and weighted sums for combining the quadratic function with the linear ones are used as parameters to implement the free search of nondominated solutions. The idea leads to the parametric linear complementarity problem formulation. An approach to deal with this type of problems is given as well. The approach is illustrated with a numerical example.     

赋序列范数的矢值序列空间ss(E)的强暴露性和暴露性

刻划了赋序列范数的矢值B anach序列空间ss(E)的强暴露性和暴露性,给出了它们的判据.     

Ratio dynamic programs

This paper considers a finite serial multistage system where the measure of effectiveness of the system is a ratio of two return functions. The numerator of the ratio is an additive return function whereas the denominator is a multiplicative one. Because of the difference in the nature of the separability of the two factors, standard parametric approaches do not generate returns which are separable. Hence, the resulting formulation cannot be solved by dynamic programming. We consider an associated two-criteria dynamic program and show that the optimal solution is a nondominated solution of the two criteria program. An efficient search algorithm through the nondominated solutions is presented to solve this class of serial multistage decision systems. Computational results are presented to demonstrate the effectiveness of this approach.     

An interactive weighted Tchebycheff procedure for multiple objective programming

The procedure samples the efficient set by computing the nondominated criterion vector that is closest to an ideal criterion vector according to a randomly weighted Tchebycheff metric. Using ‘filtering’ techniques, maximally dispersed representatives of smaller and smaller subsets of the set of nondominated criterion vectors are presented at each iteration. The procedure has the advantage that it can converge to non-extreme final solutions. Especially suitable for multiple objective linear programming, the procedure is also applicable to integer and nonlinear multiple objective programs.     

An algorithm for the bi-criterion integer programming problem

We specify a variation of the weighting method for multi-criterion optimization which determines nondominated solutions to the bi-criterion integer programming problem. The technique makes use of imposed constraints based on nondominated points. For the bi-criterion case, we develop an algorithm which finds all nondominated points by solving a sequence of single-criterion integer programming problems. We present computational results for the linear 0–1 case and discuss the extension of our algorithm to the general multi-criterion integer programming problem.     

Pyramidal tours and multiple objectives

In this study, we work on the traveling salesperson problems and bottleneck traveling salesperson problems that have special matrix structures and lead to polynomially solvable cases. We extend the problems to multiple objectives and investigate the properties of the nondominated points. We develop a pseudo-polynomial time algorithm to find a nondominated point for any number of objectives. Finally, we propose an approach to generate all nondominated points for the biobjective case.     

Using ELECTRE TRI outranking method to sort MOMILP nondominated solutions

Several interactive methods exist to identify nondominated solutions in a Multiple Objective Mixed Integer Linear Program. But what if the Decision Maker is also interested in sorting those solutions (assigning them to pre-established ordinal categories)? We propose an interactive “branch-and-bound like” technique to progressively build the nondominated set, combined with ELECTRE TRI method (Pessimistic procedure) to sort identified nondominated solutions. A disaggregation approach is considered in order to avoid direct definition of all ELECTRE TRI preference parameters. Weight-importance coefficients are inferred and category reference profiles are determined based on assignment examples provided by the Decision Maker. A computation tool was developed with a twofold purpose: support the Decision Maker involved in a decision process and provide a test bed for research purposes.     

Analysis of multiobjective decision problems by the indifference band approach

A new approach, based on indifference band, for analyzing problems with multiple objectives is described. The relations of this approach to some previous results are given. Methods for generating nondominated solutions are supplied.     

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.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.