An MOLP based procedure for finding efficient units in DEA models

In this paper a multiple objective linear programming (MOLP) problem whose feasible region is the production possibility set with variable returns to scale is proposed. By solving this MOLP problem by multicriterion simplex method, the extreme efficient Pareto points can be obtained. Then the extreme efficient units in data envelopment analysis (DEA) with variable returns to scale, considering the specified theorems and conditions, can be obtained. Therefore, by solving the proposed MOLP problem, the non-dominant units in DEA can be found. Finally, a numerical example is provided.     

Finding DEA-efficient hyperplanes using MOLP efficient faces

This paper suggests a method for finding efficient hyperplanes with variable returns to scale the technology in data envelopment analysis (DEA) by using the multiple objective linear programming (MOLP) structure. By presenting an MOLP problem for finding the gradient of efficient hyperplanes, We characterize the efficient faces. Thus, without finding the extreme efficient points of the MOLP problem and only by identifying the efficient faces of the MOLP problem, we characterize the efficient hyperplanes which make up the DEA efficient frontier. Finally, we provide an algorithm for finding the efficient supporting hyperplanes and efficient defining hyperplanes, which uses only one linear programming problem.     

An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem

Various difficulties have been encountered in using decision set-based vector maximization methods to solve a multiple objective linear programming problem (MOLP). Motivated by these difficulties, some researchers in recent years have suggested that outcome set-based approaches should instead be developed and used to solve problem (MOLP). In this article, we present a finite algorithm, called the Outer Approximation Algorithm, for generating the set of all efficient extreme points in the outcome set of problem (MOLP). To our knowledge, the Outer Approximation Algorithm is the first algorithm capable of generating this set. As a by-product, the algorithm also generates the weakly efficient outcome set of problem (MOLP). Because it works in the outcome set rather than in the decision set of problem (MOLP), the Outer Approximation Algorithm has several advantages over decision set-based algorithms. It is also relatively easy to implement. Preliminary computational results for a set of randomly-generated problems are reported. These results tangibly demonstrate the usefulness of using the outcome set approach of the Outer Approximation Algorithm instead of a decision set-based approach. This revised version was published online in July 2006 with corrections to the Cover Date.     

PROMISE: A DSS for multiple objective stochastic linear programming problems

Most of the multiple objective linear programming (MOLP) methods which have been proposed in the last fifteen years suppose deterministic contexts, but because many real problems imply uncertainty, some methods have been recently developed to deal with MOLP problems in stochastic contexts. In order to help the decision maker (DM) who is placed before such stochastic MOLP problems, we have built a Decision Support System called PROMISE. On the one hand, our DSS enables the DM to identify many current stochastic contexts: risky situations and also situations of partial uncertainty. On the other hand, according to the nature of the uncertainty, our DSS enables the DM to choose the most appropriate interactive stochastic MOLP method among the available methods, if such a method exists, and to solve his problem via the chosen method.     

Sensitivity analysis on the priority of the objective functions in lexicographic multiple objective linear programs

This paper deals with a class of multiple objective linear programs (MOLP) called lexicographic multiple objective linear programs (LMOLP). In this paper, by providing an efficient algorithm which employs the preceding computations as well, it is shown how we can solve the LMOLP problem if the priority of the objective functions is changed. In fact, the proposed algorithm is a kind of sensitivity analysis on the priority of the objective functions in the LMOLP problems.     

Random problem generation and the computation of efficient extreme points in multiple objective linear programming

This paper looks at the task of computing efficient extreme points in multiple objective linear programming. Vector maximization software is reviewed and the ADBASE solver for computing all efficient extreme points of a multiple objective linear program is described. To create MOLP test problems, models for random problem generation are discussed. In the computational part of the paper, the numbers of efficient extreme points possessed by MOLPs (including multiple objective transportation problems) of different sizes are reported. In addition, the way the utility values of the efficient extreme points might be distributed over the efficient set for different types of utility functions is investigated. Not surprisingly, results show that it should be easier to find good near-optimal solutions with linear utility functions than with, for instance, Tchebycheff types of utility functions.Dedicated to Professor George B. Dantzig on the occasion of his eightieth birthday.     

Experiments with an interactive paired comparison simplex method for molp problems

In this paper, an interactive paired comparison simplex based method formultiple objective linear programming (MOLP) problems is developed and compared to other interactive MOLP methods. The decision maker (DM)’s utility function is assumed to be unknown, but is an additive function of his known linearized objective functions. A test for ‘utility efficiency’ for MOLP problems is developed to reduce the number of efficient extreme points generated and the number of questions posed to the DM. The notion of ‘strength of preference ’ is developed for the assessment of the DM’s unknown utility function where he can express his preference for a pair of extreme points as ‘strong ’, ‘weak ’, or ‘almost indifferent ’. The problem of ‘inconsistency of the DM’ is formalized and its resolution is discussed. An example of the method and detailed computational results comparing it with other interactive MOLP methods are presented. Several performance measures for comparative evaluations of interactive multiple objective programming methods are also discussed. All rights reserved. This study, or parts thereof, may not be reproduced in any form without written permission of the authors.     

Further Analysis of an Outcome Set-Based Algorithm for Multiple-Objective Linear Programming

Various difficulties have been encountered in using decision set-based vector maximization methods to solve a multiple-objective linear programming problem (MOLP). Motivated by these difficulties, Benson recently developed a finite, outer-approximation algorithm for generating the set of all efficient extreme points in the outcome set, rather than in the decision set, of problem (MOLP). In this article, we show that the Benson algorithm also generates the set of all weakly efficient points in the outcome set of problem (MOLP). As a result, the usefulness of the algorithm as a decision aid in multiple objective linear programming is further enhanced.     

A multiple criteria approach to data envelopment analysis

In this paper, we present a Multiple Criteria Data Envelopment Analysis (MCDEA) model which can be used to improve discriminating power of DEA methods and also effectively yield more reasonable input and output weights without a priori information about the weights. In the proposed model, several different efficiency measures, including classical DEA efficiency, are defined under the same constraints. Each measure serves as a criterion to be optimized. Efficiencies are then evaluated under the framework of multiple objective linear programming (MOLP). The method is illustrated through three examples in which data sets are taken from previous research on DEA's discriminating power and weight restriction.     

带权值的模糊多目标线性规划

本文提出了求解一般多目标性规划问题 (MOL P)的带权值的模糊多目标线性规划方法 .证明了在权值都大于零的条件下 ,与 (MOLP)原问题对应的带权值的模糊多目标线性规划问题的最优解为模糊有效解 ,从而为原问题的有效解 ,并作了实例验证 .     

A new method for multiple criteria group decision making with incomplete weight information under linguistic environment

A new method is proposed to solve multiple criteria group decision making (MCGDM) problems, in which both the criteria values and criteria weights take the form of linguistic information, and the information about linguistic criteria weights is partly known or completely unknown. Firstly, to get reasonable decision result, instead of assigning the same weight to the decision maker (DM) for all criteria, we propose a method to determine the weight of DM with respect to each criterion under linguistic environment by calculating the similarity degree between individual 2-tuple linguistic evaluation value and the mean given by all decision makers (DMs). Secondly, for the situations where the information about the criteria weights is partly known or completely unknown, we establish optimization models to determine the criteria weights by defining 2-tuple linguistic positive ideal solution (TL-PIS), 2-tuple linguistic right negative ideal solution (TL-RNIS) and 2-tuple linguistic left negative ideal solution (TL-LNIS) of the collective 2-tuple linguistic decision matrix. Thirdly, we propose a new method to solve MCGDM problems with partly known or completely unknown linguistic weight information. Finally, an illustrative example is given to demonstrate the calculation process of the proposed method.     

Computing the nadir point for multiobjective discrete optimization problems

We investigate the problem of finding the nadir point for multiobjective discrete optimization problems (MODO). The nadir point is constructed from the worst objective values over the efficient set of a multiobjective optimization problem. We present a new algorithm to compute nadir values for MODO with \(p\) objective functions. The proposed algorithm is based on an exhaustive search of the \((p-2)\)-dimensional space for each component of the nadir point. We compare our algorithm with two earlier studies from the literature. We give numerical results for all algorithms on multiobjective knapsack, assignment and integer linear programming problems. Our algorithm is able to obtain the nadir point for relatively large problem instances with up to five-objectives.     

Hybrid Approach for Solving Multiple-Objective Linear Programs in Outcome Space

Various difficulties arise in using decision set-based vector maximization methods to solve a multiple-objective linear programming problem (MOLP). Motivated by these difficulties, some researchers in recent years have begun to develop tools for analyzing and solving problem (MOLP) in outcome space, rather than in decision space. In this article, we present and validate a new hybrid vector maximization approach for solving problem (MOLP) in outcome space. The approach systematically integrates a simplicial partitioning technique into an outer approximation procedure to yield an algorithm that generates the set of all efficient extreme points in the outcome set of problem (MOLP) in a finite number of iterations. Some key potential practical and computational advantages of the approach are indicated.     

Bounding MOLP objective functions: effect on efficient set size

In multiple objective linear programming (MOLP) problems the extraction of all the efficient extreme points becomes problematic as the size of the problem increases. One of the suggested actions, in order to keep the size of the efficient set to manageable limits, is the use of bounds on the values of the objective functions by the decision maker. The unacceptable efficient solutions are screened out from further investigation and the size of the efficient set is reduced. Although the bounding of the objective functions is widely used in practice, the effect of this action on the size of the efficient set has not been investigated. In this paper, we study the effect of individual and simultaneous bounding of the objective functions on the number of the generated efficient points. In order to estimate the underlying relationships, a computational experiment is designed, in which randomly generated multiple objective linear programming problems of various sizes are systematically examined.     

Gradient projection and local region search for multiobjective optimisation

This paper presents a new method for multiobjective optimisation based on gradient projection and local region search. The gradient projection is conducted through the identification of normal vectors of an efficient frontier. The projection of the gradient of a nonlinear utility function onto the tangent plane of the efficient frontier at a given efficient solution leads to the definition of a feasible local region in a neighbourhood of the solution. Within this local region, a better efficient solution may be sought. To implement such a gradient-based local region search scheme, a new auxiliary problem is developed. If the utility function is given explicitly, this search scheme results in an iterative optimisation algorithm capable of general nonseparable multiobjective optimisation. Otherwise, an interactive decision making algorithm is developed where the decision maker (DM) is expected to provide local preference information in order to determine trade-off directions and step sizes. Optimality conditions for the algorithms are established and the convergence of the algorithms is proven. A multiobjective linear programming (MOLP) problem is taken for example to demonstrate this method both graphically and analytically. A nonlinear multiobjective water quality management problem is finally examined to show the potential application of the method to real world decision problems.     

A grey relational projection method for multi-attribute decision making based on intuitionistic trapezoidal fuzzy number

With respect to multiple attribute decision making (MADM) problems in which the attribute value takes the form of intuitionistic trapezoidal fuzzy number, and the attribute weight is unknown, a new decision making analysis methods are developed. Firstly, some operational laws and expected values of intuitionistic trapezoidal fuzzy numbers, and distance between two intuitionistic trapezoidal fuzzy numbers, are introduced. Then information entropy method is used to determine the attribute weight, and the grey relational projection method combined grey relational analysis method and projection method is proposed, and to rank the alternatives are done by the relative closeness to PIS which combines grey relational projection values from the positive ideal solution and negative ideal solution to each alternative. Finally, an illustrative example is given to verify the developed approach and to demonstrate its practicality and effectiveness.     

Approximating the nondominated set of an MOLP by approximately solving its dual problem

The geometric duality theory of Heyde and Löhne (2006) defines a dual to a multiple objective linear programme (MOLP). In objective space, the primal problem can be solved by Benson’s outer approximation method (Benson 1998a,b) while the dual problem can be solved by a dual variant of Benson’s algorithm (Ehrgott et al. 2007). Duality theory then assures that it is possible to find the (weakly) nondominated set of the primal MOLP by solving its dual. In this paper, we propose an algorithm to solve the dual MOLP approximately but within specified tolerance. This approximate solution set can be used to calculate an approximation of the weakly nondominated set of the primal. We show that this set is a weakly ε-nondominated set of the original primal MOLP and provide numerical evidence that this approach can be faster than solving the primal MOLP approximately.     

On spanning tree problems with multiple objectives

We investigate two versions of multiple objective minimum spanning tree problems defined on a network with vectorial weights. First, we want to minimize the maximum ofQ linear objective functions taken over the set of all spanning trees (max-linear spanning tree problem, ML-ST). Secondly, we look for efficient spanning trees (multi-criteria spanning tree problem, MC-ST).Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees we use neighbourhood search to determine a sequence of solutions with the property that the distance between two consecutive solutions is less than a given accuracy.Partially supported by Deutsche Forschungsgemeinschaft and HCº Contract no. ERBCHRXCT 930087.Partially supported by Alexander von Humboldt-Stiftung.     

Multiobjective data envelopment analysis

Data envelopment analysis (DEA) is popularly used to evaluate relative efficiency among public or private firms. Most DEA models are established by individually maximizing each firm's efficiency according to its advantageous expectation by a ratio. Some scholars have pointed out the interesting relationship between the multiobjective linear programming (MOLP) problem and the DEA problem. They also introduced the common weight approach to DEA based on MOLP. This paper proposes a new linear programming problem for computing the efficiency of a decision-making unit (DMU). The proposed model differs from traditional and existing multiobjective DEA models in that its objective function is the difference between inputs and outputs instead of the outputs/inputs ratio. Then an MOLP problem, based on the introduced linear programming problem, is formulated for the computation of common weights for all DMUs. To be precise, the modified Chebychev distance and the ideal point of MOLP are used to generate common weights. The dual problem of this model is also investigated. Finally, this study presents an actual case study analysing R&D efficiency of 10 TFT-LCD companies in Taiwan to illustrate this new approach. Our model demonstrates better performance than the traditional DEA model as well as some of the most important existing multiobjective DEA models.