A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.     

Viscosity Solutions for a System of Integro-PDEs and Connections to Optimal Switching and Control of Jump-Diffusion Processes

We develop a viscosity solution theory for a system of nonlinear degenerate parabolic integro-partial differential equations (IPDEs) related to stochastic optimal switching and control problems or stochastic games. In the case of stochastic optimal switching and control, we prove via dynamic programming methods that the value function is a viscosity solution of the IPDEs. In our setting the value functions or the solutions of the IPDEs are not smooth, so classical verification theorems do not apply.     

A Deterministic Approach To Stochastic Optimal Control With Application To Anticipative Control

Using the decomposition of solution of SDE, we consider the stochastic optimal control problem with anticipative controls as a family of deterministic control problems parametrized by the paths of the driving Wiener process and of a newly introduced Lagrange multiplier stochastic process (nonanticipativity equality constraint). It is shown that the value function of these problems is the unique global solution of a robust equation (random partial differential equation) associated to a linear backward Hamilton-Jacobi-Bellman stochastic partial differential equation (HJB SPDE). This appears as limiting SPDE for a sequence of random HJB PDE's when linear interpolation approximation of the Wiener process is used. Our approach extends the Wong-Zakai type results [20] from SDE to the stochastic dynamic programming equation by showing how this arises as average of the limit of a sequence of deterministic dynamic programming equations. The stochastic characteristics method of Kunita [13] is used to represent the value function. By choosing the Lagrange multiplier equal to its nonanticipative constraint value the usual stochastic (nonanticipative) optimal control and optimal cost are recovered. This suggests a method for solving the anticipative control problems by almost sure deterministic optimal control. We obtain a PDE for the “cost of perfect information” the difference between the cost function of the nonanticipative control problem and the cost of the anticipative problem which satisfies a nonlinear backward HJB SPDE. Poisson bracket conditions are found ensuring this has a global solution. The cost of perfect information is shown to be zero when a Lagrangian submanifold is invariant for the stochastic characteristics. The LQG problem and a nonlinear anticipative control problem are considered as examples in this framework     

Models and model value in stochastic programming

Finding optimal decisions often involves the consideration of certain random or unknown parameters. A standard approach is to replace the random parameters by the expectations and to solve a deterministic mathematical program. A second approach is to consider possible future scenarios and the decision that would be best under each of these scenarios. The question then becomes how to choose among these alternatives. Both approaches may produce solutions that are far from optimal in the stochastic programming model that explicitly includes the random parameters. In this paper, we illustrate this advantage of a stochastic program model through two examples that are representative of the range of problems considered in stochastic programming. The paper focuses on the relative value of the stochastic program solution over a deterministic problem solution.The author's work was supported in part by the National Science Foundation under Grant DDM-9215921.     

Telecommunication Link Restoration Planning with Multiple Facility Types

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting (restoring) traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network to permit link restoration of steady-state traffic. We present a planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances that nearly achieve these worst-case bounds. In tests on three real-world problems and numerous randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. However, for small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, and our heuristic solutions are closer to optimality than implied by the gaps.     

Planning logistics operations in the oil industry

In this paper we apply stochastic programming modelling and solution techniques to planning problems for a consortium of oil companies. A multiperiod supply, transformation and distribution scheduling problem—the Depot and Refinery Optimization Problem (DROP)—is formulated for strategic or tactical level planning of the consortium's activities. This deterministic model is used as a basis for implementing a stochastic programming formulation with uncertainty in the product demands and spot supply costs (DROPS), whose solution process utilizes the deterministic equivalent linear programming problem. We employ our STOCHGEN general purpose stochastic problem generator to ‘recreate’ the decision (scenario) tree for the unfolding future as this deterministic equivalent. To project random demands for oil products at different spatial locations into the future and to generate random fluctuations in their future prices/costs a stochastic input data simulator is developed and calibrated to historical industry data. The models are written in the modelling language XPRESS-MP and solved by the XPRESS suite of linear programming solvers. From the viewpoint of implementation of large-scale stochastic programming models this study involves decisions in both space and time and careful revision of the original deterministic formulation. The first part of the paper treats the specification, generation and solution of the deterministic DROP model. The stochastic version of the model (DROPS) and its implementation are studied in detail in the second part and a number of related research questions and implications discussed.     

Optimal investment and reinsurance for an insurer under Markov-modulated financial market

This study examines optimal investment and reinsurance policies for an insurer with the classical surplus process. It assumes that the financial market is driven by a drifted Brownian motion with coefficients modulated by an external Markov process specified by the solution to a stochastic differential equation. The goal of the insurer is to maximize the expected terminal utility. This paper derives the Hamilton–Jacobi–Bellman (HJB) equation associated with the control problem using a dynamic programming method. When the insurer admits an exponential utility function, we prove that there exists a unique and smooth solution to the HJB equation. We derive the explicit optimal investment policy by solving the HJB equation. We can also find that the optimal reinsurance policy optimizes a deterministic function. We also obtain the upper bound for ruin probability in finite time for the insurer when the insurer adopts optimal policies.     

A simple recourse model for power dispatch under uncertain demand

Optimal power dispatch under uncertainty of power demand is tackled via a stochastic programming model with simple recourse. The decision variables correspond to generation policies of a system comprising thermal units, pumped storage plants and energy contracts. The paper is a case study to test the kernel estimation method in the context of stochastic programming. Kernel estimates are used to approximate the unknown probability distribution of power demand. General stability results from stochastic programming yield the asymptotic stability of optimal solutions. Kernel estimates lead to favourable numerical properties of the recourse model (no numerical integration, the optimization problem is smooth convex and of moderate dimension). Test runs based on real-life data are reported. We compute the value of the stochastic solution for different problem instances and compare the stochastic programming solution with deterministic solutions involving adjusted demand portions.This research is supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.     

Validation analysis of mirror descent stochastic approximation method

The main goal of this paper is to develop accuracy estimates for stochastic programming problems by employing stochastic approximation (SA) type algorithms. To this end we show that while running a Mirror Descent Stochastic Approximation procedure one can compute, with a small additional effort, lower and upper statistical bounds for the optimal objective value. We demonstrate that for a certain class of convex stochastic programs these bounds are comparable in quality with similar bounds computed by the sample average approximation method, while their computational cost is considerably smaller.     

The value of the stochastic solution in multistage problems

We generalize the definition of the bounds for the optimal value of the objective function for various deterministic equivalent models in multistage stochastic programs. The parameters EVPI and VSS were introduced for two-stage models. The parameter EVPI, the expected value of perfect information, measures how much it is reasonable to pay to obtain perfect information about the future. The parameter VSS, the value of the stochastic solution, allows us to obtain the goodness of the expected solution value when the expected values are replaced by the random values for the input variables. We extend the definition of these parameters to the multistage stochastic model and prove a similar chain of inequalities with the lower and upper bounds depending substantially on the structure of the problem. This research has been partially supported by the grants, 1/BBVA 00038.16421/2004 from Fundación BBVA, SEJ2005-05549/ECON from Ministerio de Educación y Ciencia and the grant GRUPOS79/04 from the Generalitat Valenciana, Spain.     

A branch and bound method for stochastic global optimization

A stochastic branch and bound method for solving stochastic global optimization problems is proposed. As in the deterministic case, the feasible set is partitioned into compact subsets. To guide the partitioning process the method uses stochastic upper and lower estimates of the optimal value of the objective function in each subset. Convergence of the method is proved and random accuracy estimates derived. Methods for constructing stochastic upper and lower bounds are discussed. The theoretical considerations are illustrated with an example of a facility location problem.     

Efficient cuts in Lagrangean ‘Relax-and-cut’ schemes

Lagrangean relaxation produces bounds on the optimal value of (mixed) integer programming problems. These bounds, together with integer feasible solution values, provide intervals bracketing the optimal value of the original problem. When the residual gap, i.e., the relative size of the interval, is too large for the approximations to be deemed satisfactory, it is desirable to ‘strengthen’ the Lagrangean bounds. One possible strengthening technique consists of identifying cuts which are violated by the current Lagrangean solution, and dualizing them. Unfortunately not every valid inequality that is currently violated will improve the Lagrangean relaxation bound when dualized. This paper investigates what makes a violated cut ‘efficient’ in improving bounds. It also provides examples of efficient cuts for several (mixed) integer programming problems.     

Optimal liquidation under partial information with price impact

We study the optimal liquidation problem in a market model where the bid price follows a geometric pure jump process whose local characteristics are driven by an unobservable finite-state Markov chain and by the liquidation rate. This model is consistent with stylized facts of high frequency data such as the discrete nature of tick data and the clustering in the order flow. We include both temporary and permanent effects into our analysis. We use stochastic filtering to reduce the optimal liquidation problem to an equivalent optimization problem under complete information. This leads to a stochastic control problem for piecewise deterministic Markov processes (PDMPs). We carry out a detailed mathematical analysis of this problem. In particular, we derive the optimality equation for the value function, we characterize the value function as continuous viscosity solution of the associated dynamic programming equation, and we prove a novel comparison result. The paper concludes with numerical results illustrating the impact of partial information and price impact on the value function and on the optimal liquidation rate.     

Inference of statistical bounds for multistage stochastic programming problems

We discuss in this paper statistical inference of sample average approximations of multistage stochastic programming problems. We show that any random sampling scheme provides a valid statistical lower bound for the optimal (minimum) value of the true problem. However, in order for such lower bound to be consistent one needs to employ the conditional sampling procedure. We also indicate that fixing a feasible first-stage solution and then solving the sampling approximation of the corresponding (T–1)-stage problem, does not give a valid statistical upper bound for the optimal value of the true problem.Supported, in part, by the National Science Foundation under grant DMS-0073770.     

A two-echelon stochastic facility location model for humanitarian relief logistics

We develop a two-stage stochastic programming model for a humanitarian relief logistics problem where decisions are made for pre- and post-disaster rescue centers, the amount of relief items to be stocked at the pre-disaster rescue centers, the amount of relief item flows at each echelon, and the amount of relief item shortage. The objective is to minimize the total cost of facility location, inventory holding, transportation and shortage. The deterministic equivalent of the model is formulated as a mixed-integer linear programming model and solved by a heuristic method based on Lagrangean relaxation. Results on randomly generated test instances show that the proposed solution method exhibits good performance up to 25 scenarios. We also validate our model by calculating the value of the stochastic solution and the expected value of perfect information.     

Dynamic asset allocation for varied financial markets under regime switching framework

Asset allocation among diverse financial markets is essential for investors especially under situations such as the financial crisis of 2008. Portfolio optimization is the most developed method to examine the optimal decision for asset allocation. We employ the hidden Markov model to identify regimes in varied financial markets; a regime switching model gives multiple distributions and this information can convert the static mean–variance model into an optimization problem under uncertainty, which is the case for unobservable market regimes. We construct a stochastic program to optimize portfolios under the regime switching framework and use scenario generation to mathematically formulate the optimization problem. In addition, we build a simple example for a pension fund and examine the behavior of the optimal solution over time by using a rolling-horizon simulation. We conclude that the regime information helps portfolios avoid risk during left-tail events.     

Classical and Impulse Control for the Optimization of Dividend and Proportional Reinsurance Policies with Regime Switching

We consider the optimal proportional reinsurance and dividend strategy. The surplus process is modeled by the classical compound Poisson risk model with regime switching. Considering a class of utility functions, the object of the insurer is to select the reinsurance and dividend strategy that maximizes the expected total discounted utility of the shareholders until ruin. By adapting the techniques and methods of stochastic control, we study the quasi-variational inequality for this classical and impulse control problem and establish a verification theorem. We show that the optimal value function is characterized as the unique viscosity solution of the corresponding quasi-variational inequality.     

A stochastic target formulation for optimal switching problems in finite horizon

We consider a general optimal switching problem for a controlled diffusion and show that its value coincides with the value of a well-suited stochastic target problem associated to a diffusion with jumps. The proof consists in showing that the Hamilton–Jacobi–Bellman equations of both problems are the same and in proving a comparison principle for this equation. This provides a new family of lower bounds for the optimal switching problem, which can be computed by Monte-Carlo methods. This result has also a nice economical interpretation in terms of a firm's valuation.     

An Optimization Model for Stochastic Project Networks with Cash Flows

Project networks – or PERT networks – can be characterized by random completion times of activities and positive or negative cash flows throughout the project. In these cases the decision maker’s problem consists of determining a feasible activities schedule, to maximize the project financial value, where the financial value is measured by the net present value (npv) of cash flows.The analysis of these networks is a difficult computational task for the following reason. First, suppose that a schedule is fixed using a heuristic rule. Then the expected npv is calculated. But, due to stochastic job completion times, this problem belongs to the ♯-P complete difficulty class, e.g. problems that involve finding all the Hamiltonian cycles in a network. The problem is such that evaluating one project alone is not sufficient, but the optimal one has to be selected. This involves a further increase in computational time.This paper proposes a stochastic optimization model to determine a heuristic scheduling rule, that provides an approximate solution to finding the optimal project npv. A feature of this approach is that the scheduling rule is completely deterministic and defined when the project begins. Therefore an upper bound of the expected npv, that is an optimistic estimate, can be calculated through linear programming and a lower bound, that is a pessimistic estimate, can be calculated using simulation before the project begins.     

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.