Belief linear programming

This paper proposes solution approaches to the belief linear programming (BLP). The BLP problem is an uncertain linear program where uncertainty is expressed by belief functions. The theory of belief function provides an uncertainty measure that takes into account the ignorance about the occurrence of single states of nature. This is the case of many decision situations as in medical diagnosis, mechanical design optimization and investigation problems. We extend stochastic programming approaches, namely the chance constrained approach and the recourse approach to obtain a certainty equivalent program. A generic solution strategy for the resulting certainty equivalent is presented.     

Stochastic utility-efficient programming of organic dairy farms

Opportunities to make sequential decisions and adjust activities as a season progresses and more information becomes available characterise the farm management process. In this paper, we present a discrete stochastic two-stage utility-efficient programming model of organic dairy farms, which includes risk aversion in the decision maker’s objective function as well as both embedded risk (stochastic programming with recourse) and non-embedded risk (stochastic programming without recourse). Historical farm accountancy data and subjective judgements were combined to assess the nature of the uncertainty that affects the possible consequences of the decisions. The programming model was used within a stochastic dominance framework to examine optimal strategies in organic dairy systems in Norway.     

Applying the minimax criterion in stochastic recourse programs

We consider an optimization problem in which some uncertain parameters are replaced by random variables. The minimax approach to stochastic programming concerns the problem of minimizing the worst expected value of the objective function with respect to the set of probability measures that are consistent with the available information on the random data. Only very few practicable solution procedures have been proposed for this problem and the existing ones rely on simplifying assumptions. In this paper, we establish a number of stability results for the minimax stochastic program, justifying in particular the approach of restricting attention to probability measures with support in some known finite set. Following this approach, we elaborate solution procedures for the minimax problem in the setting of two-stage stochastic recourse models, considering the linear recourse case as well as the integer recourse case. Since the solution procedures are modifications of well-known algorithms, their efficacy is immediate from the computational testing of these procedures and we do not report results of any computational experiments.     

On the information-based complexity of stochastic programming

Existing complexity results in stochastic linear programming using the Turing model depend only on problem dimensionality. We apply techniques from the information-based complexity literature to show that the smoothness of the recourse function is just as important. We derive approximation error bounds for the recourse function of two-stage stochastic linear programs and show that their worst case is exponential and depends on the solution tolerance, the dimensionality of the uncertain parameters and the smoothness of the recourse function.     

The optimal resource portfolio under consumer choice and demand risk for vertically differentiated products

We study the optimal resource portfolio of a firm that sells two vertically differentiated products and utilizes resource flexibility and responsive pricing. We model this decision problem as a two-stage stochastic programming problem with recourse: In the first stage, the firm determines its resource mix and capacities so as to maximize the expected profit under demand uncertainty; in the second stage, uncertainty is resolved and the firm determines its production and pricing decision, constrained by its investment decision. We show that the objective function of this decision problem is not well-behaved (ie, it may have multiple local maxima). Using the concept of Pareto dominance, we reduce the feasible investment region, without loss of optimality, to one in which the objective function is well-behaved everywhere. This reduction allows us to derive the necessary and sufficient conditions for the optimal capacity decision and to gain insights.     

On the cutting stock problem under stochastic demand

This paper addresses the one-dimensional cutting stock problem when demand is a random variable. The problem is formulated as a two-stage stochastic nonlinear program with recourse. The first stage decision variables are the number of objects to be cut according to a cutting pattern. The second stage decision variables are the number of holding or backordering items due to the decisions made in the first stage. The problem’s objective is to minimize the total expected cost incurred in both stages, due to waste and holding or backordering penalties. A Simplex-based method with column generation is proposed for solving a linear relaxation of the resulting optimization problem. The proposed method is evaluated by using two well-known measures of uncertainty effects in stochastic programming: the value of stochastic solution—VSS—and the expected value of perfect information—EVPI. The optimal two-stage solution is shown to be more effective than the alternative wait-and-see and expected value approaches, even under small variations in the parameters of the problem.     

Applications of stochastic programming: Achievements and questions

When solving a decision problem under uncertainty via stochastic programming it is essential to choose or to build a suitable stochastic programming model taking into account the nature of the real-life problem, character of input data, availability of software and computer technology. Besides a brief review of history and achievements of stochastic programming, selected modeling issues concerning applications of multistage stochastic programs with recourse (the choice of the horizon, stages, methods for generating scenario trees, etc.) will be discussed.     

Primal and dual linear decision rules in stochastic and robust optimization

Linear stochastic programming provides a flexible toolbox for analyzing real-life decision situations, but it can become computationally cumbersome when recourse decisions are involved. The latter are usually modeled as decision rules, i.e., functions of the uncertain problem data. It has recently been argued that stochastic programs can quite generally be made tractable by restricting the space of decision rules to those that exhibit a linear data dependence. In this paper, we propose an efficient method to estimate the approximation error introduced by this rather drastic means of complexity reduction: we apply the linear decision rule restriction not only to the primal but also to a dual version of the stochastic program. By employing techniques that are commonly used in modern robust optimization, we show that both arising approximate problems are equivalent to tractable linear or semidefinite programs of moderate sizes. The gap between their optimal values estimates the loss of optimality incurred by the linear decision rule approximation. Our method remains applicable if the stochastic program has random recourse and multiple decision stages. It also extends to cases involving ambiguous probability distributions.     

A Chance Constrained Approach to Fractional Programming with Random Numerator

This paper presents a chance constrained programming approach to the problem of maximizing the ratio of two linear functions of decision variables which are subject to linear inequality constraints. The coefficient parameters of the numerator of the objective function are assumed to be random variables with a known multivariate normal probability distribution. A deterministic equivalent of the stochastic linear fractional programming formulation has been obtained and a subsidiary convex program is given to solve the deterministic problem.     

Selecting tolerances in chance-constrained programming: A multiple objective linear programming approach

An importance issue concerning the practical application of chance-constrained programming is the lack of a rational method for choosing risk levels or tolerances on the chance constraints. While there has also been much recent debate on the relationship, equivalence, usefulness, and other characteristics of chance-constrained programming relative to stochastic programming with recourse, this paper focuses on the problem of improving the selection of tolerances within the chance-constrained framework. An approach is presented, based on multiple objective linear programming, which allows the decision maker to be more involved in the tolerance selection process, but does not demand a priori decisions on appropriate tolerances. An example is presented which illustrates the approach.     

Postoptimality for mean-risk stochastic mixed-integer programs and its application

The mean-risk stochastic mixed-integer programs can better model complex decision problems under uncertainty than usual stochastic (integer) programming models. In order to derive theoretical results in a numerically tractable way, the contamination technique is adopted in this paper for the postoptimality analysis of the mean-risk models with respect to changes in the scenario set, here the risk is measured by the lower partial moment. We first study the continuity of the objective function and the differentiability, with respect to the parameter contained in the contaminated distribution, of the optimal value function of the mean-risk model when the recourse cost vector, the technology matrix and the right-hand side vector in the second stage problem are all random. The postoptimality conclusions of the model are then established. The obtained results are applied to two-stage stochastic mixed-integer programs with risk objectives where the objective function is nonlinear with respect to the probability distribution. The current postoptimality results for stochastic programs are improved.     

Quantitative stability of mixed-integer two-stage quadratic stochastic programs

For our introduced mixed-integer quadratic stochastic program with fixed recourse matrices, random recourse costs, technology matrix and right-hand sides, we study quantitative stability properties of its optimal value function and optimal solution set when the underlying probability distribution is perturbed with respect to an appropriate probability metric. To this end, we first establish various Lipschitz continuity results about the value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of linear constraints. The obtained results extend earlier results about quantitative stability properties of stochastic integer programming and stability results for mixed-integer parametric quadratic programs.     

两阶段随机线性规划的费用型鲁棒模型

Vladmiron和Zenios曾引进了限制补偿的概念,给出了关于具有补偿的两阶段随机线性规划的鲁棒优化的新的表述。为适应决策者对补偿在技术操作上的稳定性与经费预算上的稳定性的需求,我们提出了费用型鲁棒模型以及混合型鲁棒模型,并转化为序列修正的线性规划的求解问题．     

Topology optimization of plane frames in case of random external loadings

Using the first collapse–theorem, the necessary and sufficient survival conditions of an elasto–plastic structure consist of the yield condition and the equilibrium condition. In practical applications several random model parameters have to be taken into account. This leads to a stochastic optimization problem which cannot be solved using the traditional methods. Instead of that, appropriate (deterministic) substitute problems must be formulated. Here, the topology optimization of frames is considered, where the external load is supposed to be stochastic. The recourse problem will be formulated in general and in the standard form of stochastic linear programming (SLP). After the formulation of the stochastic optimization problem, the recourse problem with discretization and the expected value problem are introduced as representatives of substitute problems. Subsequently, numerical results using these methods are presented. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stochastic Programming Models for Decreasing Risk Aversion

For a stochastic programming problem with simple recourse, we show how to formulate and analyze a model that encodes the common risk attitude of decreasing risk aversion. We discuss a class of linear fractional utility functions that represent this risk attitude and show that for such a utility function the resulting nonlinear model can be reduced to a linear programming model. The linear model, moreover, has only a slight percentage increase in the number of constraints as compared with the usual linear model representing risk neutrality.     

Nonnormal deterministic equivalents and a transformation in stochastic mathematical programming

This paper considers random variables of the continuous type in a stochastic programming problem and presents (1) a general approach to the development of deterministic equivalents of constraints to be satisfied within certain probability limits, and (2) a deterministic transformation of a stochastic programming problem with random variables in the objective function. Deterministic equivalents are developed for constraints containing uniform random variables, but the approach used can be applied to other types of continuous random variables, as well. When the random variables appear in the objective function, a deterministic transformation of the stochastic programming problem is obtained to yield a closed-form solution without resort to a Monte Carlo computer simulation. Extension of this approach to stochastic problems with discrete random variables and integer decision variables is discussed briefly. A numerical example is presented.     

Quantitative Stability Analysis of Two-Stage Stochastic Linear Programs with Full Random Recourse

Abstract

In this paper, we apply the parametric linear programing technique and pseudo metrics to study the quantitative stability of the two-stage stochastic linear programing problem with full random recourse. Under the simultaneous perturbation of the cost vector, coefficient matrix, and right-hand side vector, we first establish the locally Lipschitz continuity of the optimal value function and the boundedness of optimal solutions of parametric linear programs. On the basis of these results, we deduce the locally Lipschitz continuity and the upper bound estimation of the objective function of the two-stage stochastic linear programing problem with full random recourse. Then by adopting different pseudo metrics, we obtain the quantitative stability results of two-stage stochastic linear programs with full random recourse which improve the current results under the partial randomness in the second stage problem. Finally, we apply these stability results to the empirical approximation of the two-stage stochastic programing model, and the rate of convergence is presented.     

Natural gas cash-out problem: Bilevel stochastic optimization approach

A stochastic formulation of the natural gas cash-out problem is given in a form of a bilevel multi-stage stochastic programming model with recourse. After reducing the original formulation to a bilevel linear problem, a stochastic scenario tree is defined by its node events, and time series forecasting is used to produce stochastic values for data of natural gas price and demand. Numerical experiments were run to compare the stochastic solution with the perfect information solution and the expected value solutions.     

正态随机规划的确定性规划及其灵敏度分析

在大量的管理决策问题中,经常会遇到目标函数的系数和右端常数为相互独立的正态随机变量的随机线性规划模型.利用对偶规划将正态随机规划化为具有α可靠度的线性规划,给出了解决该正态随机规划的一个有效方法,并对正态随机变量的参数进行了灵敏度分析,避免了由于参数估计偏差给决策带来的风险,保证了最优方案的α可靠度.     

Distributionally robust simple integer recourse

The simple integer recourse (SIR) function of a decision variable is the expectation of the integer round-up of the shortage/surplus between a random variable with a known distribution and the decision variable. It is the integer analogue of the simple (continuous) recourse function in two-stage stochastic linear programming. Structural properties and approximations of SIR functions have been extensively studied in the seminal works of van der Vlerk and coauthors. We study a distributionally robust SIR function (DR-SIR) that considers the worst-case expectation over a given family of distributions. Under the assumption that the distribution family is specified by its mean and support, we derive a closed form analytical expression for the DR-SIR function. We also show that this nonconvex DR-SIR function can be represented using a mixed-integer second-order conic program.