Sensitivity analysis of an agricultural linear programming model

The paper presents a method of sensitivity analysis for linear systems and its practical application, allowing directs interpretation of results. The subject of analysis is a set of large regional agricultural LP models meant for rationalization of regional agricultural policies in Polish conditions. Sensitivity analysis is performed with regard to perturbations in values of elements of the LP basis matrix for a given LP solution. Software developed makes it possible to analyze solutions obtained with MPS 360 or MPSX 370. Structural approach was applied consisting in block-triangularization of the matrix defining the set of equations corresponding to the optimum vertex. The approach lowers computational burden and yields qualitative sensitivity assessment, i.e. enables exclusion of influences of certain parameters on some variables.     

Twenty years of linear programming based portfolio optimization

Markowitz formulated the portfolio optimization problem through two criteria: the expected return and the risk, as a measure of the variability of the return. The classical Markowitz model uses the variance as the risk measure and is a quadratic programming problem. Many attempts have been made to linearize the portfolio optimization problem. Several different risk measures have been proposed which are computationally attractive as (for discrete random variables) they give rise to linear programming (LP) problems. About twenty years ago, the mean absolute deviation (MAD) model drew a lot of attention resulting in much research and speeding up development of other LP models. Further, the LP models based on the conditional value at risk (CVaR) have a great impact on new developments in portfolio optimization during the first decade of the 21st century. The LP solvability may become relevant for real-life decisions when portfolios have to meet side constraints and take into account transaction costs or when large size instances have to be solved. In this paper we review the variety of LP solvable portfolio optimization models presented in the literature, the real features that have been modeled and the solution approaches to the resulting models, in most of the cases mixed integer linear programming (MILP) models. We also discuss the impact of the inclusion of the real features.     

Parametric LP for sensitivity analysis of efficiency in MOLP problems

This paper describes sensitivity analysis in multiple objective linear programming (MOLP) with one of the criteria function coefficients parameterized. The parametric linear programming (LP) is used for analyzing a range set—the parameters set for which a given feasible solution is efficient for MOLP. The main theoretical result is a presentation of convexity of the range set. Moreover, an algorithm based on some of LP problems is presented for generating the range set.     

Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard

As shown in previous work, robust linear programming problems featuring polyhedral right-hand side (RHS) uncertainty (a) arise in many practical applications; (b) frequently lead to robust equivalents belonging to the class of strongly NP-hard problems. In the present paper the case of ellipsoidal RHS uncertainty is investigated and similar complexity results are shown to hold even when restricting to simplified specially structured problems related to robust production planning under uncertain customer requirements. The proof is based on a reduction which significantly differs from the one used in the case of polyhedral RHS uncertainty.     

A new proposed model of restricted data envelopment analysis by correlation coefficients

The concept of efficiency in data envelopment analysis (DEA) is defined as weighted sum of outputs/weighted sum of inputs. In order to calculate the maximum efficiency score, each decision making unit (DMU)’s inputs and outputs are assigned to different weights. Hence, the classical DEA allows the weight flexibility. Therefore, even if they are important, the inputs or outputs of some DMUs can be assigned zero (0) weights. Thus, these inputs or outputs are neglected in the evaluation. Also, some DMUs may be defined as efficient even if they are inefficient. This situation leads to unrealistic results. Also to eliminate the problem of weight flexibility, weight restrictions are made in DEA. In our study, we proposed a new model which has not been published in the literature. We describe it as the restricted data envelopment analysis ((ARIII(COR))) model with correlation coefficients. The aim for developing this new model, is to take into account the relations between variables using correlation coefficients. Also, these relations were added as constraints to the CCR and BCC models. For this purpose, the correlation coefficients were used in the restrictions of input–output each one alone and their combination together. Inputs and outputs are related to the degree of correlation between each other in the production. Previous studies did not take into account the relationship between inputs/outputs variables. So, only with expert opinions or an objective method, weight restrictions have been made. In our study, the weights for input and output variables were determined, according to the correlations between input and output variables. The proposed new method is different from other methods in the literature, because the efficiency scores were calculated at the level of correlations between the input and/or output variables.     

Duality in Fuzzy Linear Programming: Some New Concepts and Results

A class of fuzzy linear programming (FLP) problems based on fuzzy relations is introduced, the concepts of feasible and -efficient solutions are defined. The class of crisp (classical) LP problems and interval LP problems can be embedded into the class of FLP ones. Moreover, for FLP problems a new concept of duality is introduced and the weak and strong duality theorems are derived. The previous results are applied to the special case of interval LP and compared to the existing literature.     

A sequential algorithm and error sensitivity analysis for the inverse heat conduction problems with multiple heat sources

This paper proposes a sequential approach to determine the unknown parameters for inverse heat conduction problems which have multiple time-dependent heat sources. There are two main aims in this study, one is to derive an inverse algorithm that can estimate the unknown conditions effectively, and the other is to bring up a theoretical sensitivity analysis to discuss what causes the growth of errors. This paper has three major achievements with regard to the literature on IHCPs, as follows: (1) proposing an efficient sequential inverse algorithm that can simultaneously determine several unknown time-dependent parameters; (2) exploring why the sequential function specification method can provide a stable but inaccurate estimation when tackling problems with larger measurement errors; and (3) discussing the sensitivity problem and analyzing what factors cause the growth in error sensitivity. Three examples are applied to demonstrate the performance of the proposed method, and the numerical results show that the accurate estimations can be obtained by alleviating the error sensitivity when the measurement error is considered.     

Stochastic modelling of reservoir operations

The nature of hydrologic parameters in reservoir management models is uncertain. In mathematical programming models the uncertainties are dealt with either indirectly (sensitivity analysis of a deterministic model) or directly by applying a chance-constrained type of formulation or some of the stochastic programming techniques (LP and DP based models). Various approaches are reviewed in the paper. Moran's theory of storage is an alternative stochastic modelling approach to mathematical programming techniques. The basis of the approach and its application is presented. Reliability programming is a stochastic technique based on the chance-constrained approach, where the reliabilities of the chance constraints are considered as extra decision variables in the model. The problem of random event treatment in the reservoir management model formulation using reliability programming is addressed in this paper.     

Sensitivity analysis of mixed integer programs: An application to environmental policy making

We consider a class of mixed integer programs in which the concave objective function and the constraint matrix are held fixed while some of the right hand side (RHS) coefficients are varied. An efficient iterative algorithm is developed for performing the above sensitivity analysis. A practical application of this class of programs is encountered in environmental policy making and accordingly it is used in illustrating the operation of the algorithm.     

LP models for bin packing and cutting stock problems

We review several linear programming (LP) formulations for the one-dimensional cutting stock and bin packing problems, namely, the models of Kantorovich, Gilmore–Gomory, onecut models, as in the Dyckhoff–Stadtler approach, position-indexed models, and a model derived from the vehicle routing literature.We analyse some relations between the corresponding LP relaxations, and their relative strengths, and refer how to derive branching schemes that can be used in the exact solution of these problems, using branch-and-price.     

The finite-to-finite strand of a learning progression for the concept of function: A research synthesis and cognitive analysis

In this paper we report validation efforts around the finite-to-finite strand of a provisional learning progression (LP) for the concept of function. We regard an LP as an empirically-verified account of how student understandings form over time and in response to instruction. The finite-to-finite strand of the LP was informed by literature on students’ thinking and learning related to functions as well as the Algebra Project’s curricular approach, which is designed for students who are traditionally underserved by mathematics education. Developing and validating an LP is a multi-step, cyclic process. Here we report on one step in this process, an item and response analysis. Data sources include 680 students’ responses to 13 multipart computer-delivered tasks. Results suggest that revisions to the items, associated scoring rubrics, and in some instances the LP are warranted. We illustrate this task, rubric, and LP revision process through an item analysis for a selected task.     

格值命题逻辑系统LP(X)的语法扩张

We have given a semantic extension of lattice-valued propositional logic LP(X) in [6]. In this paper, we investigate its corresponding syntactic extension of LP(X) and give the relations between these two extensions.     

Orthant tail dependence of multivariate extreme value distributions

The orthant tail dependence describes the relative deviation of upper- (or lower-) orthant tail probabilities of a random vector from similar orthant tail probabilities of a subset of its components, and can be used in the study of dependence among extreme values. Using the conditional approach, this paper examines the extremal dependence properties of multivariate extreme value distributions and their scale mixtures, and derives the explicit expressions of orthant tail dependence parameters for these distributions. Properties of the tail dependence parameters, including their relations with other extremal dependence measures used in the literature, are discussed. Various examples involving multivariate exponential, multivariate logistic distributions and copulas of Archimedean type are presented to illustrate the results.     

Weakly redundant constraints and their impact on postoptimal analyses in LP

Suppose that in a mathematical programming problem with a smooth objective function the constraints set is formed by linear inequalities. Then, as is well known, it is possible to determine redundant constraints before the optimization procedure starts. If some of the vertices of the convex polyhedron defined by the linear constraints are degenerate, the known redundancy-determining procedures may fail. Based on the recently developed theory of degeneracy graphs (DG's for short) a procedure is suggested how to proceed in degenerate cases. Weakly redundant constraints which cause degeneracy do have some impact on sensitivity analyses with respect oo the RHS or objective function coefficients. Using again the theory of DG's this impact is analysed. Also procedures are suggested how to perform sensitivity analyses when the degeneracy of the optimal vertex is not caused only by weakly redundant constraints. Small numerical examples are used for illustration.     

Capacitated facility location/network design problems

We introduce a combined facility location/network design problem in which facilities have constraining capacities on the amount of demand they can serve. This model has a number of applications in regional planning, distribution, telecommunications, energy management, and other areas. Our model includes the classical capacitated facility location problem (CFLP) on a network as a special case. We present a mixed integer programming formulation of the problem, and several classes of valid inequalities are derived to strengthen its LP relaxation. Computational experience with problems with up to 40 nodes and 160 candidate links is reported, and a sensitivity analysis provides insight into the behavior of the model in response to changes in key problem parameters.     

The one-warehouse multi-retailer problem: reformulation, classification, and computational results

We consider the one-warehouse multi-retailer problem where a warehouse replenishes multiple retailers with deterministic dynamic demands over a horizon. The problem is to determine when and how much to order to the warehouse and retailers such that the total system-wide costs are minimized. We propose a new (combined transportation and shortest path based) integer programming reformulation for the problem in addition to the echelon stock and transportation based formulations in the literature. We analyze the strength of the LP relaxations of three formulations and show that the new formulation is stronger than others. We also show that the new and transportation based formulations are equivalent for the joint replenishment problem, where the warehouse is a crossdocking facility. We extend all formulations to the case with initial inventory at the warehouse and reveal the relation among their LP relaxations. We present our computational experiments with all formulations over a set of randomly generated test instances.     

Drawdown: from practice to theory and back again

Maximum drawdown, the largest cumulative loss from peak to trough, is one of the most widely used indicators of risk in the fund management industry, but one of the least developed in the context of measures of risk. We formalize drawdown risk as Conditional Expected Drawdown (CED), which is the tail mean of maximum drawdown distributions. We show that CED is a degree one positive homogenous risk measure, so that it can be linearly attributed to factors; and convex, so that it can be used in quantitative optimization. We empirically explore the differences in risk attributions based on CED, Expected Shortfall (ES) and volatility. An important feature of CED is its sensitivity to serial correlation. In an empirical study that fits AR(1) models to US Equity and US Bonds, we find substantially higher correlation between the autoregressive parameter and CED than with ES or with volatility.     

Time-Cost Trade-Off Analysis in Some Constrained Assignment Problems

Several variations of two-dimensional (workers x jobs) and three-dimensional (workers x jobs x machines) time- as well as cost-minimizing assignment problems, which arise owing to (i) precedence relations of some form among the jobs or (ii) capacity restrictions on workers/machines imposed by the requirement that the surplus resources have to be fully employed, have been considered in the literature. In this paper, an algorithm is presented for time-cost trade-off analysis which is applicable to any general pair of such constrained problems. The algorithm is also illustrated by a numerical example.     

On solving the dual for portfolio selection by optimizing Conditional Value at Risk

This note is focused on computational efficiency of the portfolio selection models based on the Conditional Value at Risk (CVaR) risk measure. The CVaR measure represents the mean shortfall at a specified confidence level and its optimization may be expressed with a Linear Programming (LP) model. The corresponding portfolio selection models can be solved with general purpose LP solvers. However, in the case of more advanced simulation models employed for scenario generation one may get several thousands of scenarios. This may lead to the LP model with huge number of variables and constraints thus decreasing the computational efficiency of the model. To overcome this difficulty some alternative solution approaches are explored employing cutting planes or nondifferential optimization techniques among others. Without questioning importance and quality of the introduced methods we demonstrate much better performances of the simplex method when applied to appropriately rebuilt CVaR models taking advantages of the LP duality.     

基金最佳使用计划的线性规划模型

给出了基金存款策略的线性规划模型 .对基金 M使用 n年的情形 ,只需比较银行存款税后年利率 ,初步确定 n年内的一切可能有的基金存款方式及其到期本利率 ,通过基金流转分析 ,即可建立以最大奖金数为目标的线性规划模型 ( LP1 ) n;问题二则需先分析 n年内一切可行的存款和购国库卷的组合方式及其到期的最佳本利率 ,然后调整模型 ( LP1 ) .中有关的系数 ,即可得到模型 ( LP2 ) n,调整模型 ( LP1 ) n与 ( LP2 ) n中第三年的奖金 y的系数 ,即可得到问题三的线性规划模型 .本文用 SAS/OR软件求解上述模型 ,得到在 n=1 0 ,M=5 0 0 0的情形下 ,使每年奖金数为最大的各种问题的基金的最佳使用策略 .