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.     

随机逆DEA模型的输出估计研究

逆DEA模型讨论了在保持决策单元的效率指数(即最优值)不变的情况下,当输入水平给定时估计输出值.在逆DEA模型的基础上研究了效率指数提高的输出估计,讨论了带有随机因素的情况,将该问题转化成机会约束的线性规划问题,并用数值算例加以说明.     

A procedure for one-parametric linear programming

A procedure is proposed for the parametric linear programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The solution vector and the optimum value are determined explicitly as rational functions of the parameter. In addition to standard linear programming technique, only the determination of eigenvalues is required. The procedure is compared to those by Dinkelbach and Zsigmond, and a numerical example is given.     

New valid inequalities for the fixed-charge and single-node flow polytopes

The most effective software packages for solving mixed 0–1linear programs use strong valid linear inequalities derived from polyhedral theory. We introduce a new procedure which enables one to take known valid inequalities for the knapsack polytope, and convert them into valid inequalities for the fixed-charge and single-node flow polytopes. The resulting inequalities are very different from the previously known inequalities (such as flow cover and flow pack inequalities), and define facets under certain conditions.     

A mixed R&D projects and securities portfolio selection model

The business environment is full of uncertainty. Allocating the wealth among various asset classes may lower the risk of overall portfolio and increase the potential for more benefit over the long term. In this paper, we propose a mixed single-stage R&D projects and multi-stage securities portfolio selection model. Specifically, we present a bi-objective mixed-integer stochastic programming model. Moreover, we use semi-absolute deviation risk functions to measure the risk of mixed asset portfolio. Based on the idea of moments approximation method via linear programming, we propose a scenario generation approach for the mixed single-stage R&D projects and multi-stage securities portfolio selection problem. The bi-objective mixed-integer stochastic programming problem can be solved by transforming it into a single objective mixed-integer stochastic programming problem. A numerical example is given to illustrate the behavior of the proposed mixed single stage R&D projects and multi-stage securities portfolio selection model.     

A model for determining weights of traits in simultaneous multitrait selection

Simultaneous multitrait selection in plant breeding requires knowledge of the relative values, or tradeoffs, of the various traits being considered. An optimization model is developed which will allow quantification of the relative weights present in a breeder's subjective ranking of genotypes, the ranking being based on the apparent relative value of the genotypes. The model is completely general in nature. It allows specification of nonlinear solution functions as well as a linear solution function. It is not specific to any single plant species, nor is it specific to any number or type of traits. While the model is completely general, for purposes of illustration the development of the model is restricted to the linear case. The use of the model in an applied breeding experiment is illustrated using data provided by an experienced maize breeder. The data represent selected and ranked families of genotypes, where the selection and ranking criteria are the relative family performances of three traits considered of economic importance. Relative weights for the three traits are obtained from the initial ranking, and the technique is then used iteratively to demonstrate its usefulness as an interactive procedure.     

Mathematical modeling and efficient optimization methods for the distance-dependent rearrangement clustering problem

In this article we present a computational study for solving the distance-dependent rearrangement clustering problem using mixed-integer linear programming (MILP). To address sparse data sets, we present an objective function for evaluating the pair-wise interactions between two elements as a function of the distance between them in the final ordering. The physical permutations of the rows and columns of the data matrix can be modeled using mixed-integer linear programming and we present three models based on (1) the relative ordering of elements, (2) the assignment of elements to a final position, and (3) the assignment of a distance between a pair of elements. These models can be augmented with the use of cutting planes and heuristic methods to increase computational efficiency. The performance of the models is compared for three distinct re-ordering problems corresponding to glass transition temperature data for polymers and two drug inhibition data matrices. The results of the comparative study suggest that the assignment model is the most effective for identifying the optimal re-ordering of rows and columns of sparse data matrices.     

Valid inequalities for mixed-integer programmes with fixed charges on sets of variables

We consider mixed 0-1 linear programmes in which one is given a collection of (not necessarily disjoint) sets of variables and, for each set, a fixed charge is incurred if and only if at least one of the variables in the set takes a positive value. We derive strong valid linear inequalities for these problems, and show that they generalise and dominate a subclass of the well-known flow cover inequalities for the classical fixed-charge problem.     

Multiple criteria linear programming model for portfolio selection

The portfolio selection problem is usually considered as a bicriteria optimization problem where a reasonable trade-off between expected rate of return and risk is sought. In the classical Markowitz model the risk is measured with variance, thus generating a quadratic programming model. The Markowitz model is frequently criticized as not consistent with axiomatic models of preferences for choice under risk. Models consistent with the preference axioms are based on the relation of stochastic dominance or on expected utility theory. The former is quite easy to implement for pairwise comparisons of given portfolios whereas it does not offer any computational tool to analyze the portfolio selection problem. The latter, when used for the portfolio selection problem, is restrictive in modeling preferences of investors. In this paper, a multiple criteria linear programming model of the portfolio selection problem is developed. The model is based on the preference axioms for choice under risk. Nevertheless, it allows one to employ the standard multiple criteria procedures to analyze the portfolio selection problem. It is shown that the classical mean-risk approaches resulting in linear programming models correspond to specific solution techniques applied to our multiple criteria model. This revised version was published online in June 2006 with corrections to the Cover Date.     

Inverse DEA under inter-temporal dependence using multiple-objective programming

This paper deals with the inverse Data Envelopment Analysis (DEA) under inter-temporal dependence assumption. Both problems, input-estimation and output-estimation, are investigated. Necessary and sufficient conditions for input/output estimation are established utilizing Pareto and weak Pareto solutions of linear multiple-objective programming problems. Furthermore, in this paper we introduce a new optimality notion for multiple-objective programming problems, periodic weak Pareto optimality. These solutions are used in inverse DEA, and it is shown that these can be characterized by a simple modification in weighted sum scalarization tool.     

A dual simplex-based method for determination of the right and left returns to scale in DEA

This study reviews the concept of the “right” and the “left” returns to scale (RTS) in data envelopment analysis (DEA), and a dual simplex-based method, for determining these two notions in RTS, is proposed, which has computational advantages as compared to the customary method.     

MILP models for the selection of a small set of well-distributed points

Motivated by the problem of fitting a surrogate model to a set of feasible points in the context of constrained derivative-free optimization, we consider the problem of selecting a small set of points with good space-filling and orthogonality properties from a larger set of feasible points. We propose four mixed-integer linear programming models for this task and we show that the corresponding optimization problems are NP-hard. Numerical experiments show that our models consistently yield well-distributed points that, on average, help reducing the variance of model fitting errors.     

带有随机因素的逆DEA模型

本文讨论含有随机因素的逆 DEA模型 .逆 DEA模型解决的问题是 :对于某个决策单元 (DMU ) ,若增加其输入 ,在保持相对效率水平不变的情况下 ,估计 (预测 )输出应增加多少 .因此逆 DEA模型可用于短期预测问题 .带有随机因素的逆 DEA模型 ,是将该问题转化成机会约束的多目标规划问题 ,在某些特殊情况下 ,成为机会约束的线性规划问题 .     

一种可用于资金分配的线性规划模型

本运用DEA方法,给出了一种能够用来进行资金分配决策的线性规划模型,并证明了其最优解的存在性。     

Locally ideal formulations for piecewise linear functions with indicator variables

In this paper, we consider mixed integer linear programming (MIP) formulations for piecewise linear functions (PLFs) that are evaluated when an indicator variable is turned on. We describe modifications to standard MIP formulations for PLFs with desirable theoretical properties and superior computational performance in this context.     

A compromise procedure for the multiple objective linear fractional programming problem

A generalization of a well-known multiple objective linear fractional programming (MOLFP) problem, the multiple objective fractional programming (MOFP) problem, is formulated. A concept of multiple objective programming (MOP) problem corresponding to MOFP is introduced and some relations between those problems are examined. Based on these results, a compromise procedure for MOLFP problem is proposed. A numerical example is given to show how the procedure works.     

Use of DEA cross-efficiency evaluation in portfolio selection: An application to Korean stock market

We propose a way of using DEA cross-efficiency evaluation in portfolio selection. While cross efficiency is an approach developed for peer evaluation, we improve its use in portfolio selection. In addition to (average) cross-efficiency scores, we suggest to examine the variations of cross-efficiencies, and to incorporate two statistics of cross-efficiencies into the mean-variance formulation of portfolio selection. Two benefits are attained by our proposed approach. One is selection of portfolios well-diversified in terms of their performance on multiple evaluation criteria, and the other is alleviation of the so-called “ganging together” phenomenon of DEA cross-efficiency evaluation in portfolio selection. We apply the proposed approach to stock portfolio selection in the Korean stock market, and demonstrate that the proposed approach can be a promising tool for stock portfolio selection by showing that the selected portfolio yields higher risk-adjusted returns than other benchmark portfolios for a 9-year sample period from 2002 to 2011.     

A global optimization problem in portfolio selection

This paper deals with the issue of buy-in thresholds in portfolio optimization using the Markowitz approach. Optimal values of invested fractions calculated using, for instance, the classical minimum-risk problem can be unsatisfactory in practice because they lead to unrealistically small holdings of certain assets. Hence we may want to impose a discrete restriction on each invested fraction y _i such as y _i >  y _min or y _i =  0. We shall describe an approach which uses a combination of local and global optimization to determine satisfactory solutions. The approach could also be applied to other discrete conditions—for instance when assets can only be purchased in units of a certain size (roundlots).     

A procedure for parameterizing a constraint in linear programming

A post-optimal procedure for parameterizing a constraint in linear programming is proposed. In the derivation of the procedure, the technique of pivotal operations (Jordan eliminations) is applied. The procedure is compared to another by Orchard-Hays [2], and a numerical example of the procedure is provided.     

Computational strategy for Russell measure in DEA: Second-order cone programming

In aggregation for data envelopment analysis (DEA), a jointly measured efficiency score among inputs and outputs is desirable in performance analysis. A separate treatment between output-oriented efficiency and input-oriented efficiency is often needed in the conventional radial DEA models. Such radial measures usually need to measure both that a current performance attains an efficiency frontier and that all the slacks are zero on optimality. In the analytical framework of the radial measure, Russell measure is proposed to deal with such a difficulty. A major difficulty associated with the Russell measure is that it is modeled by a nonlinear programming formulation. Hence, a conventional linear programming algorithm, usually applied for DEA, cannot solve the Russell measure. This study newly proposes a reformulation of the Russell measure by a second-order cone programming (SOCP) model and applies the primal–dual interior point algorithm to solve the Russell measure.