We consider a chance constrained problem, where one seeks to minimize a convex objective over solutions satisfying, with a given (close to one) probability, a system of randomly perturbed convex constraints. Our goal is to build a computationally tractable approximation of this (typically intractable) problem, i.e., an explicitly given convex optimization program with the feasible … Read more
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 … Read more
The main focus of this paper is discussion of complexity of stochastic programming problems. We argue that two-stage (linear) stochastic programming problems with recourse can be solved with a reasonable accuracy by using Monte Carlo sampling techniques, while multi-stage stochastic programs, in general, are intractable. We also discuss complexity of chance constrained problems and multi-stage … Read more
Computing the optimal portfolio policy of an investor facing capital gains tax is a challenging problem: because the tax to be paid depends on the price at which the security was purchased (the tax basis), the optimal policy is path dependent and the size of the problem grows exponentially with the number of time periods. … Read more
Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criteria. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk criterion, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various … Read more
This paper considers robust optimization to cope with uncertainty about the stock return process in one period portfolio selection problems involving options. The ro- bust approach relates portfolio choice to uncertainty, making more cautious portfolios when uncertainty is high. We represent uncertainty by a set of plausible expected returns of the underlyings and show that … Read more
This paper develops a solution strategy for two-stage stochastic programs with integer recourse. The proposed methodology relies on approximating the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. We show that the proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially … Read more
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 value of the true problem. However, in order for such lower bound to be consistent one needs to employ the conditional sampling procedure. … Read more
We investigate the quality of solutions obtained from sample-average approximations to two-stage stochastic linear programs with recourse. We use a recently developed software tool executing on a computational grid to solve many large instances of these problems, allowing us to obtain high-quality solutions and to verify optimality and near-optimality of the computed solutions in various … Read more
The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. … Read more