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.     

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.     

Variable preference modeling with ideal-symmetric convex cones

Based on the concept of general domination structures, this paper presents an approach to model variable preferences for multicriteria optimization and decision making problems. The preference assumptions for using a constant convex cone are given, and, in remedy of some immanent model limitations, a new set of assumptions is presented. The underlying preference model is derived as a variable domination structure that is defined by a collection of ideal-symmetric convex cones. Necessary and sufficient conditions for nondominance are established, and the problem of finding corresponding nondominated solutions is addressed and solved on examples.     

Necessary and sufficient conditions for local and global nondominated solutions in decision problems with multi-objectives

In this paper, the decision problem with multi-objectives is considered, and the nondominated solutions associated with a polyhedral domination cone are discussed. The necessary and sufficient conditions for the solutions are given in the decision space rather than the objective space. The similarity of the solution conditions obtained in this article to the Kuhn-Tucker condition of a convex programming problem is examined. As an application of the solution condition, an algorithm to locate the set of all nondominated solutions is shown for the linear multi-objective decision problem.The author would like to thank the reviewer for his helpful comments.     

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.     

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.     

Some results about nondominated solutions

We will prove that, in the case where all the domination cones are closed and convex, have a nonempty interior, and are totally ordered with respect to inclusion, the set of weakly nondominated outcomes of a nonempty convex compact setY R ⁿ is connected. Further, we give a relationship between weakly nondominated and nondominated solutions.The author would like to thank the referees for their valuable comments.     

具有控制结构的向量均衡问题与解集的性质

提出一种具有控制结构的向量均衡问题与向量映射的新的伪单调性概念,得到具有控制结构的向量均衡问题解的存在性及其解集的紧凸性．作为应用,得到具有控制结构的向量变分不等式与互补问题的解．     

Characterizations of Variable Domination Structures via Nonlinear Scalarization

In this paper, a nonlinear scalarization function is introduced for a variable domination structure. It is shown that this function is positively homogeneous, subadditive, and strictly monotone. This nonlinear function is then applied to characterize the weakly nondominated solution of multicriteria decision making problems and the solution of vector variational inequalities.     

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.     

On the existence of efficient points in locally convex spaces

We study the existence of efficient points in a locally convex space ordered by a convex cone. New conditions are imposed on the ordering cone such that for a set which is closed and bounded in the usual sense or with respect to the cone, the set of efficient points is nonempty and the domination property holds.     

ProperD-solutions of multiobjective programming problems with set functions

A special class of solutions for multiobjective programming problems with set functions is considered. A subset of nondominated solutions, called properD-solution set, with respect to a given domination structure is characterized under two situations, with and without inequality constraints.The authors greatly appreciate valuable comments received from the referees.     

Total domination dot-stable graphs

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Two vertices of G are said to be dotted (identified) if they are combined to form one vertex whose open neighborhood is the union of their neighborhoods minus themselves. We note that dotting any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most 2. A graph is total domination dot-stable if dotting any pair of adjacent vertices leaves the total domination number unchanged. We characterize the total domination dot-stable graphs and give a sharp upper bound on their total domination number. We also characterize the graphs attaining this bound.     

Total domination critical and stable graphs upon edge removal

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination edge critical if the removal of any arbitrary edge increases the total domination number. On the other hand, a graph is total domination edge stable if the removal of any arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge critical graphs. We also investigate various properties of total domination edge stable graphs.     

An approximation algorithm for convex multi-objective programming problems

In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable objectives or constraints.     

Generating equidistant representations in biobjective programming

In recent years, emphasis has been placed on generating quality representations of the nondominated set of multiobjective optimization problems. This paper presents two methods for generating discrete representations with equidistant points for biobjective problems with solution sets determined by convex, polyhedral cones. The Constraint Controlled-Spacing method is based on the epsilon-constraint method with an additional constraint to control the spacing of generated points. The Bilevel Controlled-Spacing method has a bilevel structure with the lower-level generating the nondominated points and the upper-level controlling the spacing, and is extended to multiobjective problems. Both methods are proven to produce (weakly) nondominated points and are demonstrated on a variety of test problems.     

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.     

Total domination stable graphs upon edge addition

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination edge addition stable if the addition of an arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge addition stable graphs. We determine a sharp upper bound on the total domination number of total domination edge addition stable graphs, and we determine which combinations of order and total domination number are attainable. We finish this work with an investigation of claw-free total domination edge addition stable graphs.     

Characterizations of trees with equal paired and double domination numbers

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, and a double dominating set is a dominating set that dominates every vertex of G at least twice. We show that for trees, the paired-domination number is less than or equal to the double domination number, solving a conjecture of Chellali and Haynes. Then we characterize the trees having equal paired and double domination numbers.     

The disjunctive domination number of a graph

Abstract

For a positive integer b, we define a set S of vertices in a graph G as a b-disjunctive dominating set if every vertex not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it. The b-disjunctive domination number is the minimum cardinality of such a set. This concept is motivated by the concepts of distance domination and exponential domination. In this paper, we start with some simple results, then establish bounds on the parameter especially for regular graphs and claw-free graphs. We also show that determining the parameter is NP-complete, and provide a linear-time algorithm for trees.