A new robust DEA model and super-efficiency measure

Applications of traditional data envelopments analysis (DEA) models require knowledge of crisp input and output data. However, the real-world problems often deal with imprecise or ambiguous data. In this paper, the problem of considering uncertainty in the equality constraints is analyzed and by using the equivalent form of CCR model, a suitable robust DEA model is derived in order to analyze the efficiency of decision-making units (DMUs) under the assumption of uncertainty in both input and output spaces. The new model based on the robust optimization approach is suggested. Using the proposed model, it is possible to evaluate the efficiency of the DMUs in the presence of uncertainty in a fewer steps compared to other models. In addition, using the new proposed robust DEA model and envelopment form of CCR model, two linear robust super-efficiency models for complete ranking of DMUs are proposed. Two different case studies of different contexts are taken as numerical examples in order to compare the proposed model with other approaches. The examples also illustrate various possible applications of new models.     

Dynamic pricing and inventory control: robust vs. stochastic uncertainty models—a computational study

In this paper, we consider a variety of models for dealing with demand uncertainty for a joint dynamic pricing and inventory control problem in a make-to-stock manufacturing system. We consider a multi-product capacitated, dynamic setting, where demand depends linearly on the price. Our goal is to address demand uncertainty using various robust and stochastic optimization approaches. For each of these approaches, we first introduce closed-loop formulations (adjustable robust and dynamic programming), where decisions for a given time period are made at the beginning of the time period, and uncertainty unfolds as time evolves. We then describe models in an open-loop setting, where decisions for the entire time horizon must be made at time zero. We conclude that the affine adjustable robust approach performs well (when compared to the other approaches such as dynamic programming, stochastic programming and robust open loop approaches) in terms of realized profits and protection against constraint violation while at the same time it is computationally tractable. Furthermore, we compare the complexity of these models and discuss some insights on a numerical example.     

A robust von Neumann minimax theorem for zero-sum games under bounded payoff uncertainty

The celebrated von Neumann minimax theorem is a fundamental theorem in two-person zero-sum games. In this paper, we present a generalization of the von Neumann minimax theorem, called robust von Neumann minimax theorem, in the face of data uncertainty in the payoff matrix via robust optimization approach. We establish that the robust von Neumann minimax theorem is guaranteed for various classes of bounded uncertainties, including the matrix 1-norm uncertainty, the rank-1 uncertainty and the columnwise affine parameter uncertainty.     

A robust data envelopment analysis model with different scenarios

Input and output data, under uncertainty, must be taken into account as an essential part of data envelopment analysis (DEA) models in practice. Many researchers have dealt with this kind of problem using fuzzy approaches, DEA models with interval data or probabilistic models. This paper presents an approach to scenario-based robust optimization for conventional DEA models. To consider the uncertainty in DEA models, different scenarios are formulated with a specified probability for input and output data instead of using point estimates. The robust DEA model proposed is aimed at ranking decision-making units (DMUs) based on their sensitivity analysis within the given set of scenarios, considering both feasibility and optimality factors in the objective function. The model is based on the technique proposed by Mulvey et al. (1995) for solving stochastic optimization problems. The effect of DMUs on the product possibility set is calculated using the Monte Carlo method in order to extract weights for feasibility and optimality factors in the goal programming model. The approach proposed is illustrated and verified by a case study of an engineering company.     

Chance constrained uncertain classification via robust optimization

This paper studies the problem of constructing robust classifiers when the training is plagued with uncertainty. The problem is posed as a Chance-Constrained Program (CCP) which ensures that the uncertain data points are classified correctly with high probability. Unfortunately such a CCP turns out to be intractable. The key novelty is in employing Bernstein bounding schemes to relax the CCP as a convex second order cone program whose solution is guaranteed to satisfy the probabilistic constraint. Prior to this work, only the Chebyshev based relaxations were exploited in learning algorithms. Bernstein bounds employ richer partial information and hence can be far less conservative than Chebyshev bounds. Due to this efficient modeling of uncertainty, the resulting classifiers achieve higher classification margins and hence better generalization. Methodologies for classifying uncertain test data points and error measures for evaluating classifiers robust to uncertain data are discussed. Experimental results on synthetic and real-world datasets show that the proposed classifiers are better equipped to handle data uncertainty and outperform state-of-the-art in many cases.     

Robust optimization and portfolio selection: The cost of robustness

Robust optimization is a tractable alternative to stochastic programming particularly suited for problems in which parameter values are unknown, variable and their distributions are uncertain. We evaluate the cost of robustness for the robust counterpart to the maximum return portfolio optimization problem. The uncertainty of asset returns is modelled by polyhedral uncertainty sets as opposed to the earlier proposed ellipsoidal sets. We derive the robust model from a min-regret perspective and examine the properties of robust models with respect to portfolio composition. We investigate the effect of different definitions of the bounds on the uncertainty sets and show that robust models yield well diversified portfolios, in terms of the number of assets and asset weights.     

Adaptive and robust radiation therapy optimization for lung cancer

A previous approach to robust intensity-modulated radiation therapy (IMRT) treatment planning for moving tumors in the lung involves solving a single planning problem before the start of treatment and using the resulting solution in all of the subsequent treatment sessions. In this paper, we develop an adaptive robust optimization approach to IMRT treatment planning for lung cancer, where information gathered in prior treatment sessions is used to update the uncertainty set and guide the reoptimization of the treatment for the next session. Such an approach allows for the estimate of the uncertain effect to improve as the treatment goes on and represents a generalization of existing robust optimization and adaptive radiation therapy methodologies. Our method is computationally tractable, as it involves solving a sequence of linear optimization problems. We present computational results for a lung cancer patient case and show that using our adaptive robust method, it is possible to attain an improvement over the traditional robust approach in both tumor coverage and organ sparing simultaneously. We also prove that under certain conditions our adaptive robust method is asymptotically optimal, which provides insight into the performance observed in our computational study. The essence of our method – solving a sequence of single-stage robust optimization problems, with the uncertainty set updated each time – can potentially be applied to other problems that involve multi-stage decisions to be made under uncertainty.     

Robust best approximation with interpolation constraints under ellipsoidal uncertainty: Strong duality and nonsmooth Newton methods

In this paper we present a duality approach for finding a robust best approximation from a set involving interpolation constraints and uncertain inequality constraints in a Hilbert space that is immunized against the data uncertainty using a nonsmooth Newton method. Following the framework of robust optimization, we assume that the input data of the inequality constraints are not known exactly while they belong to an ellipsoidal data uncertainty set. We first show that finding a robust best approximation is equivalent to solving a second-order cone complementarity problem by establishing a strong duality theorem under a strict feasibility condition. We then examine a nonsmooth version of Newton’s method and present their convergence analysis in terms of the metric regularity condition.     

Forecasting seasonal time series data: a Bayesian model averaging approach

A flexible Bayesian periodic autoregressive model is used for the prediction of quarterly and monthly time series data. As the unknown autoregressive lag order, the occurrence of structural breaks and their respective break dates are common sources of uncertainty these are treated as random quantities within the Bayesian framework. Since no analytical expressions for the corresponding marginal posterior predictive distributions exist a Markov Chain Monte Carlo approach based on data augmentation is proposed. Its performance is demonstrated in Monte Carlo experiments. Instead of resorting to a model selection approach by choosing a particular candidate model for prediction, a forecasting approach based on Bayesian model averaging is used in order to account for model uncertainty and to improve forecasting accuracy. For model diagnosis a Bayesian sign test is introduced to compare the predictive accuracy of different forecasting models in terms of statistical significance. In an empirical application, using monthly unemployment rates of Germany, the performance of the model averaging prediction approach is compared to those of model selected Bayesian and classical (non)periodic time series models.     

Robust portfolio selection involving options under a “ marginal+joint ” ellipsoidal uncertainty set

In typical robust portfolio selection problems, one mainly finds portfolios with the worst-case return under a given uncertainty set, in which asset returns can be realized. A too large uncertainty set will lead to a too conservative robust portfolio. However, if the given uncertainty set is not large enough, the realized returns of resulting portfolios will be outside of the uncertainty set when an extreme event such as market crash or a large shock of asset returns occurs. The goal of this paper is to propose robust portfolio selection models under so-called “ marginal+joint” ellipsoidal uncertainty set and to test the performance of the proposed models. A robust portfolio selection model under a “marginal + joint” ellipsoidal uncertainty set is proposed at first. The model has the advantages of models under the separable uncertainty set and the joint ellipsoidal uncertainty set, and relaxes the requirements on the uncertainty set. Then, one more robust portfolio selection model with option protection is presented by combining options into the proposed robust portfolio selection model. Convex programming approximations with second-order cone and linear matrix inequalities constraints to both models are derived. The proposed robust portfolio selection model with options can hedge risks and generates robust portfolios with well wealth growth rate when an extreme event occurs. Tests on real data of the Chinese stock market and simulated options confirm the property of both the models. Test results show that (1) under the “ marginal+joint” uncertainty set, the wealth growth rate and diversification of robust portfolios generated from the first proposed robust portfolio model (without options) are better and greater than those generated from Goldfarb and Iyengar’s model, and (2) the robust portfolio selection model with options outperforms the robust portfolio selection model without options when some extreme event occurs.     

Portfolio selection under model uncertainty: a penalized moment-based optimization approach

We present a new approach that enables investors to seek a reasonably robust policy for portfolio selection in the presence of rare but high-impact realization of moment uncertainty. In practice, portfolio managers face difficulty in seeking a balance between relying on their knowledge of a reference financial model and taking into account possible ambiguity of the model. Based on the concept of Distributionally Robust Optimization (DRO), we introduce a new penalty framework that provides investors flexibility to define prior reference models using the distributional information of the first two moments and accounts for model ambiguity in terms of extreme moment uncertainty. We show that in our approach a globally-optimal portfolio can in general be obtained in a computationally tractable manner. We also show that for a wide range of specifications our proposed model can be recast as semidefinite programs. Computational experiments show that our penalized moment-based approach outperforms classical DRO approaches in terms of both average and downside-risk performance using historical data.     

Robust Farkas’ lemma for uncertain linear systems with applications

We present a robust Farkas lemma, which provides a new generalization of the celebrated Farkas lemma for linear inequality systems to uncertain conical linear systems. We also characterize the robust Farkas lemma in terms of a generalized characteristic cone. As an application of the robust Farkas lemma we establish a characterization of uncertainty-immunized solutions of conical linear programming problems under uncertainty.     

Robust Capacity Assignment in Telecommunications

In telecommunications, the demand is a key data that drives network planning. The demand exhibits considerable variability, due to customers movement and introduction of new services and products in the present competitive markets. To deal with this uncertainty, we consider capacity assignment problem in telecommunications in the framework of robust optimization proposed in Ben-Tal and Nemcrovski (Math Oper Res 23(4):769–805, 1998, MPS-SIAM series on optimization, 2001) and Kouvelis and Yu. We propose a decomposition scheme based on cutting plane methods. Some preliminary computational experiments indicate that the Elzinga–Moore cutting plane method (Elzinga and Moore in Math Program 8:134–145, 1975) can be a valuable choice. Since in some situations different possible uncertainty sets may exist, we propose a generalization of these models to cope at a time with a finite number of plausible uncertainty sets. A weight is associated with each uncertainty set to determine its relative importance or worth against another.     

An evidential approach to SLAM,path planning,and active exploration

Probability theory has become the standard framework in the field of mobile robotics because of the inherent uncertainty associated with sensing and acting. In this paper, we show that the theory of belief functions with its ability to distinguish between different types of uncertainty is able to provide significant advantages over probabilistic approaches in the context of robotics. We do so by presenting solutions to the essential problems of simultaneous localization and mapping (SLAM) and planning based on belief functions. For SLAM, we show how the joint belief function over the map and the robot's poses can be factored and efficiently approximated using a Rao-Blackwellized particle filter, resulting in a generalization of the popular probabilistic FastSLAM algorithm. Our SLAM algorithm produces occupancy grid maps where belief functions explicitly represent additional information about missing and conflicting measurements compared to probabilistic grid maps. The basis for this SLAM algorithm are forward and inverse sensor models, and we present general evidential models for range sensors like sonar and laser scanners. Using the generated evidential grid maps, we show how optimal decisions can be made for path planning and active exploration. To demonstrate the effectiveness of our evidential approach, we apply it to two real-world datasets where a mobile robot has to explore unknown environments and solve different planning problems. Finally, we provide a quantitative evaluation and show that the evidential approach outperforms a probabilistic one both in terms of map quality and navigation performance.     

Constructively simple estimating: a project management example

A ‘constructively simple’ approach to estimating uses a decision support modelling paradigm based on project risk management and operational research concepts. It employs probability models selected from a set of alternative stochastic models of uncertainty with a view to maximising the insight provided, given an appropriate level of complexity. It addresses issues that include the joint use of subjective and objective probabilities, subjectivity of model data and structure, bias, data acquisition costs, the importance of getting an estimate right, optimising the estimating processes involved as a whole in approximate but robust terms, and differences in interpretation of what this means to estimators and users of estimates. Specific applications are necessarily context-specific to some extent, but the underlying ideas are of general applicability. This paper uses a simple example involving estimating the uncertain duration of a project activity to illustrate what is involved.     

Generalized light robustness and the trade-off between robustness and nominal quality

Robust optimization considers optimization problems with uncertainty in the data. The common data model assumes that the uncertainty can be represented by an uncertainty set. Classic robust optimization considers the solution under the worst case scenario. The resulting solutions are often too conservative, e.g. they have high costs compared to non-robust solutions. This is a reason for the development of less conservative robust models. In this paper we extract the basic idea of the concept of light robustness originally developed in Fischetti and Monaci (Robust and online large-scale optimization, volume 5868 of lecture note on computer science. Springer, Berlin, pp 61–84, 2009) for interval-based uncertainty sets and linear programs: fix a quality standard for the nominal solution and among all solutions satisfying this standard choose the most reliable one. We then use this idea in order to formulate the concept of light robustness for arbitrary optimization problems and arbitrary uncertainty sets. We call the resulting concept generalized light robustness. We analyze the concept and discuss its relation to other well-known robustness concepts such as strict robustness (Ben-Tal et al. in Robust optimization. Princeton University Press, Princeton, 2009), reliability (Ben-Tal and Nemirovski in Math Program A 88:411–424, 2000) or the approach of Bertsimas and Sim (Oper Res 52(1):35–53, 2004). We show that the light robust counterpart is computationally tractable for many different types of uncertainty sets, among them polyhedral or ellipsoidal uncertainty sets. We furthermore discuss the trade-off between robustness and nominal quality and show that non-dominated solutions with respect to nominal quality and robustness can be computed by the generalized light robustness approach.     

A note on conflict of information and subexponential densities

The Bayesian approach allows for uncertainty about both the model and the prior settings. Such uncertainty can only be stated by probability distributions. The adoption of robust distributions deals with potential conflict of information between the prior and the data. In this paper, we present sufficient conditions for a conflict to be solved in favour of either source of information in terms of subexponential densities.     

Robust optimization in spline regression models for multi-model regulatory networks under polyhedral uncertainty

In our study, we integrate the data uncertainty of real-world models into our regulatory systems and robustify them. We newly introduce and analyse robust time-discrete target–environment regulatory systems under polyhedral uncertainty through robust optimization. Robust optimization has reached a great importance as a modelling framework for immunizing against parametric uncertainties and the integration of uncertain data is of considerable importance for the model’s reliability of a highly interconnected system. Then, we present a numerical example to demonstrate the efficiency of our new robust regression method for regulatory networks. The results indicate that our approach can successfully approximate the target–environment interaction, based on the expression values of all targets and environmental factors.     

A robustness approach to uncapacitated network design problems

In this paper, we address uncapacitated network design problems characterised by uncertainty in the input data. Network design choices have a determinant impact on the effectiveness of the system. Design decisions are frequently made with a great degree of uncertainty about the conditions under which the system will be required to operate. Instead of finding optimal designs for a given future scenario, designers often search for network configurations that are “good” for a variety of likely future scenarios. This approach is referred to as the “robustness” approach to system design. We present a formal definition of “robustness” for the uncapacitated network design problem, and develop algorithms aimed at finding robust network designs. These algorithms are adaptations of the Benders decomposition methodology that are tailored so they can efficiently identify robust network designs. We tested the proposed algorithms on a set of randomly generated problems. Our computational experiments showed two important properties. First, robust solutions are abundant in uncapacitated network design problems, and second, the proposed algorithms performance is satisfactory in terms of cost and number of robust network designs obtained.