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.     

Approximating infinite horizon stochastic optimal control in discrete time with constraints

Traditional approaches to solving stochastic optimal control problems involve dynamic programming, and solving certain optimality equations. When recast as stochastic programming problems, structural aspects such as convexity are retained, and numerical solution procedures based on decomposition and duality may be exploited. This paper explores a class of stationary, infinite-horizon stochastic optimization problems with discounted cost criterion. Constraints on both states and controls are permitted, and modeled in the objective function by allowing it to take infinite values. Approximating techniques are developed using variational analysis, and intuitive lower bounds are obtained via averaging the future. These bounds could be used in a finite-time horizon stochastic programming setting to find solutions numerically. Research supported in part by a grant of the National Science Foundation. AMS Classification 46N10, 49N15, 65K10, 90C15, 90C46     

Dynamic Capacity Acquisition and Assignment under Uncertainty

Given a set of m resources and n tasks, the dynamic capacity acquisition and assignment problem seeks a minimum cost schedule of capacity acquisitions for the resources and the assignment of resources to tasks, over a given planning horizon of T periods. This problem arises, for example, in the integrated planning of locations and capacities of distribution centers (DCs), and the assignment of customers to the DCs, in supply chain applications. We consider the dynamic capacity acquisition and assignment problem in an environment where the assignment costs and the processing requirements for the tasks are uncertain. Using a scenario based approach, we develop a stochastic integer programming model for this problem. The highly non-convex nature of this model prevents the application of standard stochastic programming decomposition algorithms. We use a recently developed decomposition based branch-and-bound strategy for the problem. Encouraging preliminary computational results are provided.     

A stochastic programming approach for planning horizons of infinite horizon capacity planning problems

Planning horizon is a key issue in production planning. Different from previous approaches based on Markov Decision Processes, we study the planning horizon of capacity planning problems within the framework of stochastic programming. We first consider an infinite horizon stochastic capacity planning model involving a single resource, linear cost structure, and discrete distributions for general stochastic cost and demand data (non-Markovian and non-stationary). We give sufficient conditions for the existence of an optimal solution. Furthermore, we study the monotonicity property of the finite horizon approximation of the original problem. We show that, the optimal objective value and solution of the finite horizon approximation problem will converge to the optimal objective value and solution of the infinite horizon problem, when the time horizon goes to infinity. These convergence results, together with the integrality of decision variables, imply the existence of a planning horizon. We also develop a useful formula to calculate an upper bound on the planning horizon. Then by decomposition, we show the existence of a planning horizon for a class of very general stochastic capacity planning problems, which have complicated decision structure.     

Mean-field stochastic control with elephant memory in finite and infinite time horizon

ABSTRACT

Our purpose of this paper is to study stochastic control problems for systems driven by mean-field stochastic differential equations with elephant memory, in the sense that the system (like the elephants) never forgets its history. We study both the finite horizon case and the infinite time horizon case.

• In the finite horizon case, results about existence and uniqueness of solutions of such a system are given. Moreover, we prove sufficient as well as necessary stochastic maximum principles for the optimal control of such systems. We apply our results to solve a mean-field linear quadratic control problem.

• For infinite horizon, we derive sufficient and necessary maximum principles.

  As an illustration, we solve an optimal consumption problem from a cash flow modelled by an elephant memory mean-field system.

     

ON THE CONVEXITY OF VALUE FUNCTIONS FOR A CERTAIN CLASS OF STOCHASTIC DYNAMIC PROGRAMMING PROBLEM

It is a common practice in stochastic dynamic programming problems to assume a priori that the value function is either concave or convex and later verify this assumption after the value function has been identified. It is often a difficult task to establish the concavity or convexity of the value function directly. In this paper, we prove that the value function of a certain type of infinite horizon stochastic dynamic programming problem is convex. This type of value function arises frequently in economic modeling.     

Two storage inventory model in a mixed environment

Multi-item inventory models with two storage facility and bulk release pattern are developed with linearly time dependent demand in a finite time horizon under crisp, stochastic and fuzzy-stochastic environments. Here different inventory parameters—holding costs, ordering costs, purchase costs, etc.—are assumed as probabilistic or fuzzy in nature. In particular cases stochastic and crisp models are derived. Models are formulated as profit maximization principle and three different approaches are proposed for solution. In the first approach, fuzzy extension principle is used to find membership function of the objective function and then it’s Graded Mean Integration Value (GMIV) for different optimistic levels are taken as equivalent stochastic objectives. Then the stochastic model is transformed to a constraint multi-objective programming problem using Stochastic Non-linear Programming (SNLP) technique. The multi-objective problems are transferred to single objective problems using Interactive Fuzzy Satisfising (IFS) technique. Finally, a Region Reducing Genetic Algorithm (RRGA) based on entropy has been developed and implemented to solve the single objective problems. In the second approach, the above GMIV (which is stochastic in nature) is optimized with some degree of probability and using SNLP technique model is transferred to an equivalent single objective crisp problem and solved using RRGA. In the third approach, objective function is optimized with some degree of possibility/necessity and following this approach model is transformed to an equivalent constrained stochastic programming problem. Then it is transformed to an equivalent single objective crisp problem using SNLP technique and solved via RRGA. The models are illustrated with some numerical examples and some sensitivity analyses have been presented.     

Two-stage stochastic lot-sizing problem under cost uncertainty

For production planning problems, cost parameters can be uncertain due to marketing activities and interest rate fluctuation. In this paper, we consider a single-item two-stage stochastic lot-sizing problem under cost parameter uncertainty. Assuming cost parameters will increase or decrease after time period p each with certain probability, we minimize the total expected cost for a finite horizon problem. We develop an extended linear programming formulation in a higher dimensional space that can provide integral solutions by showing that its constraint matrix is totally unimodular. We also project this extended formulation to a lower dimensional space and obtain a corresponding extended formulation in the lower dimensional space. Final computational experiments demonstrate that the extended formulation is more efficient and performs more stable than the two-stage stochastic mixed-integer programming formulation.     

Portfolio optimization in a Lévy market with intertemporal substitution and transaction costs

We investigate an infinite horizon investment-consumption model in which a single agent consumes and distributes her wealth between a risk-free asset (bank account) and several risky assets (stocks) whose prices are governed by Lévy (jump-diffusion) processes. We suppose that transactions between the assets incur a transaction cost proportional to the size of the transaction. The problem is to maximize the total utility of consumption under Hindy-Huang-Kreps intertemporal preferences. This portfolio optimisation problem is formulated as a singular stochastic control problem and is solved using dynamic programming and the theory of viscosity solutions. The associated dynamic programming equation is a second order degenerate elliptic integro-differential variational inequality subject to a state constraint boundary condition. The main result is a characterization of the value function as the unique constrained viscosity solution of the dynamic programming equation. Emphasis is put on providing a framework that allows for a general class of Lévy processes. Owing to the complexity of our investment-consumption model, it is not possible to derive closed form solutions for the value function. Hence, the optimal policies cannot be obtained in closed form from the first order conditions for the dynamic programming equation. Therefore, we have to resort to numerical methods for computing the value function as well as the associated optimal policies. In view of the viscosity solution theory, the analysis found in this paper will ensure the convergence of a large class of numerical methods for the investment-consumption model in question.     

A Primal-Dual Decomposition Algorithm for Multistage Stochastic Convex Programming

This paper presents a new and high performance solution method for multistage stochastic convex programming. Stochastic programming is a quantitative tool developed in the field of optimization to cope with the problem of decision-making under uncertainty. Among others, stochastic programming has found many applications in finance, such as asset-liability and bond-portfolio management. However, many stochastic programming applications still remain computationally intractable because of their overwhelming dimensionality. In this paper we propose a new decomposition algorithm for multistage stochastic programming with a convex objective and stochastic recourse matrices, based on the path-following interior point method combined with the homogeneous self-dual embedding technique. Our preliminary numerical experiments show that this approach is very promising in many ways for solving generic multistage stochastic programming, including its superiority in terms of numerical efficiency, as well as the flexibility in testing and analyzing the model.Research supported by Hong Kong RGC Earmarked Grant CUHK4233/01E.     

Sufficient Stochastic Maximum Principle for the Optimal Control of Semi-Markov Modulated Jump-Diffusion with Application to Financial Optimization

The finite state semi-Markov process is a generalization over the Markov chain in which the sojourn time distribution is any general distribution. In this article, we provide a sufficient stochastic maximum principle for the optimal control of a semi-Markov modulated jump-diffusion process in which the drift, diffusion, and the jump kernel of the jump-diffusion process is modulated by a semi-Markov process. We also connect the sufficient stochastic maximum principle with the dynamic programming equation. We apply our results to finite horizon risk-sensitive control portfolio optimization problem and to a quadratic loss minimization problem.     

Short-term electricity procurement: A rolling horizon stochastic programming approach

This paper addresses the problem faced by a large electricity consumer in determining the optimal procurement plan over a short-term time horizon. The inherent complexity of the problem, due to its dynamic and stochastic nature, is dealt by means of the stochastic programming modeling framework. In particular, a two-stage problem is formulated with the aim of establishing the optimal amount of electricity to be purchased through bilateral contracts and in the Day-Ahead Electricity Market. Recourse actions are used to hedge against uncertainty related to future electricity prices and consumer’s needs. The optimal plan is defined so to minimize the overall cost and to control risk, which is measured in the form of violation of budget constraints. The stochastic model is dynamically solved in a rolling horizon fashion by iteratively considering more and more recent information and a planning horizon of decreasing length. Extensive numerical experiments have been carried out to assess the performance of the proposed dynamic decision approach. The results collected considering a real test case are very encouraging and provide evidence of the superiority of the approach also in comparison with other alternative procurement strategies.     

A theory of rolling horizon decision making

In this paper, we develop a theoretical framework for the common business practice of rolling horizon decision making. The main idea of our approach is that the usefulness of rolling horizon methods is, to a great extent, implied by the fact that forecasting the future is a costly activity. We, therefore, consider a general, discrete-time, stochastic dynamic optimization problem in which the decision maker has the possibility to obtain information on the uncertain future at given cost. For this non-standard optimization problem with optimal stopping decisions, we develop a dynamic programming formulation. We treat both finite and infinite horizon cases. We also provide a careful interpretation of the dynamic programming equations and illustrate our results by a simple numerical example. Various generalizations are shown to be captured by straightforward modifications of our model.This research is supported in part by NSERC Grant A4619, SSHRC Grant 410-87-0524, and Manufacturing Research Corporation of Ontario. Comments and suggestions from Qing Zhang and the referees are gratefully acknowledged.     

Multistage stochastic demand-side management for price-making major consumers of electricity in a co-optimized energy and reserve market

In this paper, we take an optimization-driven heuristic approach, motivated by dynamic programming, to solve a class of non-convex multistage stochastic optimization problems. We apply this to the problem of optimizing the timing of energy consumption for a large manufacturer who is a price-making major consumer of electricity. We introduce a mixed-integer program that co-optimizes consumption bids and interruptible load reserve offers, for such a major consumer over a finite time horizon. By utilizing Lagrangian methods, we decompose our model through approximately pricing the constraints that link the stages together. We construct look-up tables in the form of consumption-utility curves, and use these to determine optimal consumption levels. We also present heuristics, in order to tackle the non-convexities within our model, and improve the accuracy of our policies. In the second part of the paper, we present stochastic solution methods for our model in which, we reduce the size of the scenario tree by utilizing a tailor-made scenario clustering method. Furthermore, we report on a case study that implements our models for a major consumer in the (full) New Zealand Electricity Market and present numerical results.     

A stochastic control model of investment,production, and consumption on a finite horizon

In this paper, we consider a stochastic control problem on a finite time horizon. The unit price of capital obeys a logarithmic Brownian motion, and the income from production is also subject to the random Brownian fluctuations. The goal is to choose optimal investment and consumption policies to maximize the finite horizon expected discounted hyperbolic absolute risk aversion utility of consumption. A dynamic programming principle is used to derive a time‐dependent Hamilton–Jacobi–Bellman equation. The Leray–Schauder fixed point theorem is used to obtain existence of solution of the HJB equation. At last, we derive the optimal investment and consumption policies by the verification theorem. The main contribution in this paper is the use of PDE technique to the finite time problem for obtaining optimal polices. Copyright © 2014 John Wiley & Sons, Ltd.     

A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem

This paper considers the mobile facility routing and scheduling problem with stochastic demand (MFRSPSD). The MFRSPSD simultaneously determines the route and schedule of a fleet of mobile facilities which serve customers with uncertain demand to minimize the total cost generated during the planning horizon. The problem is formulated as a two-stage stochastic programming model, in which the first stage decision deals with the temporal and spatial movement of MFs and the second stage handles how MFs serve customer demands. An algorithm based on the multicut version of the L-shaped method is proposed in which several lower bound inequalities are developed and incorporated into the master program. The computational results show that the algorithm yields a tighter lower bound and converges faster to the optimal solution. The result of a sensitivity analysis further indicates that in dealing with stochastic demand the two-stage stochastic programming approach has a distinctive advantage over the model considering only the average demand in terms of cost reduction.     

Stochastische Modelle zur optimalen Lastverteilung in einem Kraftwerksverbund

Kurzfassung Die Lastverteilung in einem Kraftwerksverbund erfolgt in zwei Schritten. Im ersten Schritt werden die Kraftwerkseinheiten ausgewählt, die zu jedem Zeitpunkt des Planungszeitraumes in Betrieb sind, damit die erwartete Energieanforderung erfüllt werden kann (Einsatzoptimierung). Im zweiten Schritt wird die Last, die in einem bestimmten Zeitpunkt tatsächlich anfällt, auf die in Betrieb befindlichen Einheiten verteilt (Belastungsoptimierung). Die Einsatzoptimierung erfolgt gewöhnlich mit Hilfe eines gemischt-ganzzahligen linearen Programms und die Belastungsoptimierung mit dem sogenannten Zuwachskostenverfahren. In diesem Aufsatz werden stochastische Modelle für die Einsatz- und Belastungsoptimierung formuliert.

---

The economic operation of an electric power system over a short time horizon involves two separate steps. The first of these is the predispatch or selection of equipment to be operated to meet the expected loads at each point in time of the horizon (unit commitment). The second step is the on-line economic dispatch which determines, instant to instant, the load to be carried on each unit selected in the first step. The unit commitment problem is usually solved by mixed integer programming and the economic dispatch problem by an incremental cost method. In this paper stochastic programming models for the unit commitment and economic dispatch problems are presented.

---

     

Portfolio Optimization Models on Infinite-Time Horizon

A portfolio optimization problem on an infinite-time horizon is considered. Risky asset prices obey a logarithmic Brownian motion and interest rates vary according to an ergodic Markov diffusion process. The goal is to choose optimal investment and consumption policies to maximize the infinite-horizon expected discounted hyperbolic absolute risk aversion (HARA) utility of consumption. The problem is then reduced to a one-dimensional stochastic control problem by virtue of the Girsanov transformation. A dynamic programming principle is used to derive the dynamic programming equation (DPE). The subsolution/supersolution method is used to obtain existence of solutions of the DPE. The solutions are then used to derive the optimal investment and consumption policies. In addition, for a special case, we obtain the results using the viscosity solution method.     

Variational Inequalities for Combined Control and Stopping Game

Abstract

We study a nonlinear elliptic variational inequality associated with the combined stochastic control problem. By using the dynamic programming principle and the method of penalization, we establish the existence of a unique viscosity solution of the variational inequality and describe it as the value function of the corresponding combined stochastic game problem.     

Quantitative stability of full random two-stage problems with quadratic recourse

ABSTRACT

In this paper, we discuss quantitative stability of two-stage stochastic programs with quadratic recourse where all parameters in the second-stage problem are random. By establishing the Lipschitz continuity of the feasible set mapping of the restricted Wolfe dual of the second-stage quadratic programming in terms of the Hausdorff distance, we prove the local Lipschitz continuity of the integrand of the objective function of the two-stage stochastic programming problem and then establish quantitative stability results of the optimal values and the optimal solution sets when the underlying probability distribution varies under the Fortet–Mourier metric. Finally, the obtained results are applied to study the asymptotic behaviour of the empirical approximation of the model.