Decision-dependent probabilities in stochastic programs with recourse

Stochastic programming with recourse usually assumes uncertainty to be exogenous. Our work presents modelling and application of decision-dependent uncertainty in mathematical programming including a taxonomy of stochastic programming recourse models with decision-dependent uncertainty. The work includes several ways of incorporating direct or indirect manipulation of underlying probability distributions through decision variables in two-stage stochastic programming problems. Two-stage models are formulated where prior probabilities are distorted through an affine transformation or combined using a convex combination of several probability distributions. Additionally, we present models where the parameters of the probability distribution are first-stage decision variables. The probability distributions are either incorporated in the model using the exact expression or by using a rational approximation. Test instances for each formulation are solved with a commercial solver, BARON, using selective branching.     

Dynamic Programming and Inventory Problems

After an introductory discussion of the usefulness of the technique of dynamic programming in solving practical problems of multi-stage decision processes, the paper describes its application to inventory problems. In particular, the effect of allowing the number of decision stages to increase indefinitely is investigated, and it is shown that under certain realistic conditions this situation can be dealt with. It appears to be generally true that the average cost per period will converge, for an optimal policy, as the number of periods considered increases indefinitely, and that it is feasible to search for the policy which minimizes this long-term average cost. The paper concludes with a specific example, in which it is shown that only eight iterations were necessary to find a reasonable approximation to the optimal re-order policy.     

A two-stage fuzzy robust integer programming approach for capacity planning of environmental management systems

In this study, a two-stage fuzzy robust integer programming (TFRIP) method has been developed for planning environmental management systems under uncertainty. This approach integrates techniques of robust programming and two-stage stochastic programming within a mixed integer linear programming framework. It can facilitate dynamic analysis of capacity-expansion planning for waste management facilities within a multi-stage context. In the modeling formulation, uncertainties can be presented in terms of both possibilistic and probabilistic distributions, such that robustness of the optimization process could be enhanced. In its solution process, the fuzzy decision space is delimited into a more robust one by specifying the uncertainties through dimensional enlargement of the original fuzzy constraints. The TFRIP method is applied to a case study of long-term waste-management planning under uncertainty. The generated solutions for continuous and binary variables can provide desired waste-flow-allocation and capacity-expansion plans with a minimized system cost and a maximized system feasibility.     

Optimal two-stage ordering policy with Bayesian information updating

We investigate in this paper an optimal two-stage ordering policy for seasonal products. Before the selling season, a retailer can place orders for a seasonal product from her supplier at two distinct stages satisfying the lead-time requirement. Market information is collected at the first stage and is used to update the demand forecast at the second stage by using Bayesian approach. The ordering cost at the first stage is known but the ordering cost at the second stage is uncertain. A two-stage dynamic optimization problem is formulated and an optimal policy is derived using dynamic programming. The optimal ordering policy exhibits nice structural properties and can easily be implemented by a computer program. The detailed implementation scheme is proposed. The service level and profit uncertainty level under the optimal policy are discussed. Extensive numerical analyses are carried out to study the performance of the optimal policy.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

A multi-level Taguchi-factorial two-stage stochastic programming approach for characterization of parameter uncertainties and their interactions: An application to water resources management

This paper presents a multi-level Taguchi-factorial two-stage stochastic programming (MTTSP) approach for supporting water resources management under parameter uncertainties and their interactions. MTTSP is capable of performing uncertainty analysis, policy analysis, factor screening, and interaction detection in a comprehensive and systematic way. A water resources management problem is used to demonstrate the applicability of the proposed approach. The results indicate that interval solutions can be generated for the objective function and decision variables, and a variety of decision alternatives can be obtained under different policy scenarios. The experimental data obtained from the Taguchi’s orthogonal array design are helpful in identifying the significant factors affecting the total net benefit. Then the findings from the multi-level factorial experiment reveal the latent interactions among those important factors and their curvature effects on the model response. Such a sequential strategy of experimental designs is useful in analyzing the interactions for a large number of factors in a computationally efficient manner.     

Linear programming under uncertainty: A basic property of the optimal solution

Summary We show that if the two-stage linear programming problem under uncertainty has an optimal solution, then it has an optimal solution in which the column vectors corresponding to the positive first stage decision variables are linearly independent. This leads to the result that if an optimal solution exists, then there exists an optimal solution in which not more than m + ¯m of the first stage decision variables are positive. These results extend to the multi-stage case.This research was partially supported by the Office of Naval Research under Contract Nonr-222(83), the National Science Foundation under Contract GP-4593, the Army Research Office under Contract DA-31-124-ARO-D-331 and the University of California. Reproduction in whole or part is permitted for any purpose of the United States Government.     

基于预约模式的移动充电车实时需求响应策略研究

预约模式下移动充电车实时需求响应问题是移动充电行业发展过程中的新问题,该问题包含了两类不同特点、存在动态交替影响关系的需求,不仅有时间窗约束、实时响应性要求,也有动态不确定性的特点。针对以上问题特点,本文以最大化整体收益为目标,提出联动的两阶段实时需求响应策略,引用近似动态规划求解决策未来价值,并融入到以下两阶段中：第一阶段基于多阶段随机动态决策模型与禁忌搜索算法生成了可以动态调整的充电服务方案;第二阶段基于第一阶段提出了针对动态需求的实时响应决策流程。最后,对比实验验证了本策略在不同客户规模与动态度下的有效性,并得出管理启示。本研究可以支持制定移动充电车的实时需求响应策略,对类似具有动态特征的需求响应问题具有启发意义。     

Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution

In many planning problems under uncertainty the uncertainties are decision-dependent and resolve gradually depending on the decisions made. In this paper, we address a generic non-convex MINLP model for such planning problems where the uncertain parameters are assumed to follow discrete distributions and the decisions are made on a discrete time horizon. In order to account for the decision-dependent uncertainties and gradual uncertainty resolution, we propose a multistage stochastic programming model in which the non-anticipativity constraints in the model are not prespecified but change as a function of the decisions made. Furthermore, planning problems consist of several scenario subproblems where each subproblem is modeled as a nonconvex mixed-integer nonlinear program. We propose a solution strategy that combines global optimization and outer-approximation in order to optimize the planning decisions. We apply this generic problem structure and the proposed solution algorithm to several planning problems to illustrate the efficiency of the proposed method with respect to the method that uses only global optimization.     

Convergent Bounds for Stochastic Programs with Expected Value Constraints

This article describes a bounding approximation scheme for convex multistage stochastic programs (MSP) that constrain the conditional expectation of some decision-dependent random variables. Expected value constraints of this type are useful for modelling a decision maker’s risk preferences, but they may also arise as artifacts of stage-aggregation. We develop two finite-dimensional approximate problems that provide bounds on the (infinite-dimensional) original problem, and we show that the gap between the bounds can be made smaller than any prescribed tolerance. Moreover, the solutions of the approximate MSPs give rise to a feasible policy for the original MSP, and this policy’s optimality gap is shown to be smaller than the difference of the bounds. The considered problem class comprises models with integrated chance constraints and conditional value-at-risk constraints. No relatively complete recourse is assumed.     

Newton-type methods for stochastic programming

Stochastic programming is concerned with practical procedures for decision making under uncertainty, by modelling uncertainties and risks associated with decision in a form suitable for optimization. The field is developing rapidly with contributions from many disciplines such as operations research, probability and statistics, and economics. A stochastic linear program with recourse can equivalently be formulated as a convex programming problem. The problem is often large-scale as the objective function involves an expectation, either over a discrete set of scenarios or as a multi-dimensional integral. Moreover, the objective function is possibly nondifferentiable. This paper provides a brief overview of recent developments on smooth approximation techniques and Newton-type methods for solving two-stage stochastic linear programs with recourse, and parallel implementation of these methods. A simple numerical example is used to signal the potential of smoothing approaches.     

Inventory control and pricing for perishable products under age and price dependent stochastic demand

Multistage stochastic programming (SP) with both endogenous and exogenous uncertainties is a novel problem in which some uncertain parameters are decision-dependent and others are independent of decisions. The main difficulty of this problem is that nonanticipativity constraints (NACs) make up a significantly large constraint set, growing very fast with the number of scenarios and leading to an intractable model. Usually, a lot of these constraints are redundant and hence, identification and elimination of redundant NACs can cause a significant reduction in the problem size. Recently, a polynomial time algorithm has been proposed in the literature which is able to identify all redundant NACs in an SP problem with only endogenous uncertainty. In this paper, however, we extend the algorithm proposed in the literature and present a new method which is able to make the upper most possible reduction in the number of NACs in any SP with both exogenous and endogenous uncertain parameters. Proving the validity of this method is another innovation of this study. Computational results confirm that the proposed approach can significantly reduce the problem size within a reasonable computation time.     

Lower bounding aggregation and direct computation for an infinite horizon one-reservoir model

We present a specialized policy iteration method for the computation of optimal and approximately optimal policies for a discrete-time model of a single reservoir whose discharges generate hydroelectric power. The model is described in (Lamond et al., 1995) and (Drouin et al., 1996), where the special structure of optimal policies is given and an approximate value iteration method is presented, using piecewise affine approximations of the optimal return functions. Here, we present a finite method for computing an optimal policy in O(n³) arithmetic operations, where n is the number of states in the associated Markov decision process, and a finite method for computing a lower bound on the optimal value function in O(m²n) where m is the number of nodes of the piecewise affine approximation.     

Investment and the dynamic cost of income uncertainty: The case of diminishing expectations in agriculture

This paper studies optimal investment and the dynamic cost of income uncertainty, applying a stochastic programming approach. The motivation is given by a case study in Finnish agriculture. The investment decision of a representative farm is modelled as a Markov decision process, extended to account for risk. A numerical framework for studying the dynamic uncertainty cost is presented, modifying the classical expected value of perfect information to a dynamic setting. The uncertainty cost depends on the volatility of income: e.g. with stationary income, the dynamic uncertainty cost corresponds to a dynamic option value of postponing investment. The model can be applied to agricultural policy planning. In the case study, the investment decision is sensitive to risk.     

Constraint programming for stochastic inventory systems under shortage cost

One of the most important policies adopted in inventory control is the replenishment cycle policy. Such a policy provides an effective means of damping planning instability and coping with demand uncertainty. In this paper we develop a constraint programming approach able to compute optimal replenishment cycle policy parameters under non-stationary stochastic demand, ordering, holding and shortage costs. We show how in our model it is possible to exploit the convexity of the cost-function during the search to dynamically compute bounds and perform cost-based filtering. Our computational experience show the effectiveness of our approach. Furthermore, we use the optimal solutions to analyze the quality of the solutions provided by an existing approximate mixed integer programming approach that exploits a piecewise linear approximation for the cost function.     

Continuous-Time Markov Decision Processes with State-Dependent Discount Factors

We consider continuous-time Markov decision processes in Polish spaces. The performance of a control policy is measured by the expected discounted reward criterion associated with state-dependent discount factors. All underlying Markov processes are determined by the given transition rates which are allowed to be unbounded, and the reward rates may have neither upper nor lower bounds. By using the dynamic programming approach, we establish the discounted reward optimality equation (DROE) and the existence and uniqueness of its solutions. Under suitable conditions, we also obtain a discounted optimal stationary policy which is optimal in the class of all randomized stationary policies. Moreover, when the transition rates are uniformly bounded, we provide an algorithm to compute (or?at least to approximate) the discounted reward optimal value function as well as a discounted optimal stationary policy. Finally, we use an example to illustrate our results. Specially, we first derive an explicit and exact solution to the DROE and an explicit expression of a discounted optimal stationary policy for such an example.     

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.     

Options strategies for international portfolios with overall risk management via multi-stage stochastic programming

This paper proposes a multi-stage stochastic programming model to explore optimal options strategies for international portfolios with overall risk management on Greek letters, extending existing Greek-based analysis to dynamic and nondeterministic programming under uncertainty. The contribution to the existing literature are overall control on the time-varying Greek letters, state-contingent decision dynamics in consistent with the projected outcomes of the changing information, and a holistic view for optimizing the portfolio of assets and options. Empirical results show the model possesses considerable benefits in terms of larger profit margins, greater stability of returns and higher hedging efficiency compared to traditional methods.     

Computational complexity of stochastic programming problems

Stochastic programming is the subfield of mathematical programming that considers optimization in the presence of uncertainty. During the last four decades a vast quantity of literature on the subject has appeared. Developments in the theory of computational complexity allow us to establish the theoretical complexity of a variety of stochastic programming problems studied in this literature. Under the assumption that the stochastic parameters are independently distributed, we show that two-stage stochastic programming problems are ♯P-hard. Under the same assumption we show that certain multi-stage stochastic programming problems are PSPACE-hard. The problems we consider are non-standard in that distributions of stochastic parameters in later stages depend on decisions made in earlier stages. Supported by the EPSRC grant ``Phase Transitions in the Complexity of Randomised Algorithms', by the EC IST project RAND-APX, and by the MRT Network ADONET of the European Community (MRTN-CT-2003-504438).     

Re-solving stochastic programming models for airline revenue management

We study some mathematical programming formulations for the origin-destination model in airline revenue management. In particular, we focus on the traditional probabilistic model proposed in the literature. The approach we study consists of solving a sequence of two-stage stochastic programs with simple recourse, which can be viewed as an approximation to a multi-stage stochastic programming formulation to the seat allocation problem. Our theoretical results show that the proposed approximation is robust, in the sense that solving more successive two-stage programs can never worsen the expected revenue obtained with the corresponding allocation policy. Although intuitive, such a property is known not to hold for the traditional deterministic linear programming model found in the literature. We also show that this property does not hold for some bid-price policies. In addition, we propose a heuristic method to choose the re-solving points, rather than re-solving at equally-spaced times as customary. Numerical results are presented to illustrate the effectiveness of the proposed approach.