Stochastic programs over trees with random arc capacities
NetworksPublished 1 May 1994
Warren B. Powell, Raymond K. Cheung
Citations31
SJR quartileQ1
SJR score0.87
SNIP1.24
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper develops an efficient procedure to obtain the expected recourse function exactly for single-stage problems and shows that for large trees n-stage networks can be solved more easily than can a single- stage network with n-levels.
Abstract
Abstract In this paper, we study a special class of stochastic programs where the recourse problem consists of trees with random arc capacities, which we call tree recourse. We develop an efficient procedure to obtain the expected recourse function exactly for single‐stage problems. This procedure is used in a backward recursion to find the exact expected recourse function for multistage trees. We show that for large trees n ‐stage networks can be solved more easily than can a single‐stage network with n ‐levels. We also show that the expected recourse functions for single‐stage and n ‐stage formulations of the same network can be quite similar. Finally, we illustrate the potential of using the tree recourse problems in a more general stochastic network problem. © 1994 by John Wiley & Sons, Inc.
Keywords
Social SciencesEngineering
Mathematics of Operations ResearchScenarios and Policy Aggregation in Optimization Under Uncertainty
1,335 Citations1991R. T. Rockafellar, Roger J.‐B. Wets
This paper develops for the first time a rigorous algorithmic procedure for determining a robust decision policy in response to any weighting of the scenarios.
SIAM Journal on Applied Mathematics<i>L</i>-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
1,238 Citations1969Richard M. Van Slyke, Roger J.‐B. Wets
An algorithm for L-shaped linear programs which arise naturally in optimal control problems with state constraints and stochastic linear programs (which can be represented in this form with an infinite number of linear constraints) is given.
European Journal of Operational ResearchVehicle routing: Methods and studies
814 Citations1989Jakob Krarup
Springer series in computational mathematicsNumerical Techniques for Stochastic Optimization
637 Citations1988Y. Ermoliev, Wets, R.J.-B.
This is a comprehensive and timely overview of the numerical techniques that have been developed to solve stochastic programming problems and comprehensively covers all major advances in the field (both Western and Soviet).
Mathematics of Operations ResearchStochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse
460 Citations1991Julia L. Higle, Suvrajeet Sen
A cutting plane algorithm for two-stage stochastic linear programs with recourse that uses randomly generated observations of random variables to construct statistical estimates of supports of the objective function and establishes the convergence of the algorithm under relatively mild assumptions.
Stochasticsstochastic quasigradient methods and their application to system optimization<sup>†</sup>
281 Citations1983Yuri Ermoliev
Stochastic quasigradient methods generalize the well-known stochastic approximation methods for uncnstrained optimization of the expectation of a random function to problems involving general constraints for deterministic nonlinear optimization problems.
Transportation ScienceA Successive Linear Approximation Procedure for Stochastic, Dynamic Vehicle Allocation Problems
150 Citations1990Linos F. Frantzeskakis, Warren B. Powell
The paper presents computational results that were obtained by employing a Rolling Horizon Procedure to simulate the operation of the truckload carrier and indicates the superiority of the new algorithm over other approaches tested.
Operations ResearchFormulating Two-Stage Stochastic Programs for Interior Point Methods
123 Citations1991Irvin J. Lustig, John M. Mulvey +1 more
An approach for modeling two-stage stochastic programs that yields a form suitable for interior point algorithms by replacing first stage variables with sparse "split variables" in conjunction with side-constraints is described.
Mathematics of Operations ResearchSingle-Machine Scheduling Polyhedra with Precedence Constraints
81 Citations1991Maurice Queyranne, Yaoguang Wang
The main result is a complete description of the minimal linear system defining P when the precedence constraints are series-parallel, which consists of two classes of facet-inducing inequalities, associated with series and parallel compositions, respectively.
NetworksSolving stochastic programs with network recourse
63 Citations1986Stein W. Wallace
The Schur complement for networks is developed, which is how to solve a large number of networks where the only differences are the amounts supplied and demanded at the nodes.
NetworksBounds on expected performance of networks with links subject to failure
47 Citations1984Malachy Carey, Chris Hendrickson
Mathematical ProgrammingA piecewise linear upper bound on the network recourse function
45 Citations1987Stein W. Wallace
A new piecewise linear upper bound is presented on this function, called the network recourse function, which is compared to the standard Madansky bound, and is shown computationally to be a little weaker, but much faster to find.
Operations ResearchComputational Algorithms for Convex Stochastic Programs with Simple Recourse
42 Citations1970William T. Ziemba
The algorithms presented apply when the preference functions h(x) and g(y) are convex, and continuously differentiable, k is a convex polytope, ξ has a distribution that satisfies mild convergence conditions, and the objective is to minimize the expectation of the sum of the two preference functions.
NetworksInvesting in arcs in a network to maximize the expected max flow
21 Citations1987Stein W. Wallace
This work shows how the problem of investing in new arcs in such a network in order to increase the expected max flow as much as possible can be formulated as a stochastic program with network recourse.
Operations Research LettersA factoring approach for the stochastic shortest path problem
14 Citations1991Kelly J. Hayhurst, Douglas R. Shier
This approach is based on the concept of structural factoring, in which a stochastic network is decomposed into an equivalent set of smaller, generally less complex subnetworks, which allows the exact solution of networks previously analyzed only by approximation techniques to be found.
Operations Research LettersBounding the expected time-cost curve for a stochastic pert network from below
13 Citations1989Stein W. Wallace
It is demonstrated how it is possible to instead find a curve that bounds the true expected time-cost curve from below by showing how the necessary cuts can be generated based on different bounding procedures from the literature.
Mathematical programming studiesAn alternating method for stochastic linear programming with simple recourse
6 Citations1986Liqun Qi
A method which alternates between solving some n-dimensional linear sub programs and some m-dimensional convex subprograms, where n is the dimension of the decision vector and m is thedimension of the random demand vector, which converges in finitely many steps.