The value of the stochastic solution in stochastic linear programs with fixed recourse

Stochastic linear programs have been rarely used in practical situations largely because of their complexity. In evaluating these problems without finding the exact solution, a common method has been to find bounds on the expected value of perfect information. In this paper, we consider a different method. We present bounds on the value of the stochastic solution, that is, the potential benefit from solving the stochastic program over solving a deterministic program in which expected values have replaced random parameters. These bounds are calculated by solving smaller programs related to the stochastic recourse problem.This paper is an extension of part of the author's dissertation in the Department of Operations Research, Stanford University, Stanford, California. The research was supported at Stanford by the Department of Energy under Contract DE-AC03-76SF00326, PA#DE-AT03-76ER72018, Office of Naval Research under Contract N00014-75-C-0267 and the National Science Foundation under Grants MCS76-81259, MCS-7926009 and ECS-8012974 (formerly ENG77-06761).     

Solving geometric programs using GRG: Results and comparisons

This paper describes the performance of a general-purpose GRG code for nonlinear programming in solving geometric programs. The main conclusions drawn from the experiments reported are: (i) GRG competes well with special-purpose geometric programming codes in solving geometric programs; and (ii) standard time, as defined by Colville, is an inadequate means of compensating for different computing environments while comparing optimization algorithms.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865, the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18, and the National Science Foundation, Grant No. DCR75-04544 at Stanford University; and by the Office of Naval Research under Contract No. N00014-75-C-0240, and the National Science Foundation, Grant No. SOC74-23808, at Case Western Reserve University.     

Sublinear upper bounds for stochastic programs with recourse

Separable sublinear functions are used to provide upper bounds on the recourse function of a stochastic program. The resulting problem's objective involves the inf-convolution of convex functions. A dual of this problem is formulated to obtain an implementable procedure to calculate the bound. Function evaluations for the resulting convex program only require a small number of single integrations in contrast with previous upper bounds that require a number of function evaluations that grows exponentially in the number of random variables. The sublinear bound can often be used when other suggested upper bounds are intractable. Computational results indicate that the sublinear approximation provides good, efficient bounds on the stochastic program objective value.This research has been partially supported by the National Science Foundation. The first author's work was also supported in part by Office of Naval Research Grant N00014-86-K-0628 and by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Bounding separable recourse functions with limited distribution information

The recourse function in a stochastic program with recourse can be approximated by separable functions of the original random variables or linear transformations of them. The resulting bound then involves summing simple integrals. These integrals may themselves be difficult to compute or may require more information about the random variables than is available. In this paper, we show that a special class of functions has an easily computable bound that achieves the best upper bound when only first and second moment constraints are available.This research has been partially supported by the National Science Foundation under Grants ECS-8304065 and ECS-8815101, by the Office of Naval Research Grant N00014-86-K-0628 and by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

The empirical behavior of sampling methods for stochastic programming

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 ways. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant 9726385. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant DMS-0073770. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grants 9726385 and 0082065.     

Local convergence of interior-point algorithms for degenerate monotone LCP

Most asymptotic convergence analysis of interior-point algorithms for monotone linear complementarity problems assumes that the problem is nondegenerate, that is, the solution set contains a strictly complementary solution. We investigate the behavior of these algorithms when this assumption is removed.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234.The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Multi-stage stochastic linear programs for portfolio optimization

The paper demonstrates how multi-period portfolio optimization problems can be efficiently solved as multi-stage stochastic linear programs. A scheme based on a blending of classical Benders decomposition techniques and a special technique, called importance sampling, is used to solve this general class of multi-stochastic linear programs. We discuss the case where stochastic parameters are dependent within a period as well as between periods. Initial computational results are presented.Research and reproduction of this report were partially supported by the Office of Naval Research Contract N00014-89-J-1659; the National Science Foundation Grants ECS-8906260, DMS-8913089, the Electric Power Research Institute Contract RP-8010-09, CSA-4O05335, and the Austrian Science Foundation, Fonds zur Förderung der wissenschaftlichen Forschung, Grant J0323-Phy. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do NOT necessarily reflect the views of the above sponsors. The comments of anonymous referees are gratefully acknowledged.     

A lift-and-project cutting plane algorithm for mixed 0–1 programs

We propose a cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.The research underlying this report was supported by National Science Foundation Grant #DDM-8901495 and Office of Naval Research Contract N00014-85-K-0198.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Stochastic programming with simple integer recourse

Stochastic integer programs are notoriously difficult. Very few properties are known and solution algorithms are very scarce. In this paper, we introduce the class of stochastic programs with simple integer recourse, a natural extension of the simple recourse case extensively studied in stochastic continuous programs.Analytical as well as computational properties of the expected recourse function of simple integer recourse problems are studied. This includes sharp bounds on this function and the study of the convex hull. Finally, a finite termination algorithm is obtained that solves two classes of stochastic simple integer recourse problems.Supported by the National Operations Research Network in the Netherlands (LNMB).     

A weighted gram-schmidt method for convex quadratic programming

Range-space methods for convex quadratic programming improve in efficiency as the number of constraints active at the solution decreases. In this paper we describe a range-space method based upon updating a weighted Gram-Schmidt factorization of the constraints in the active set. The updating methods described are applicable to both primal and dual quadratic programming algorithms that use an active-set strategy. Many quadratic programming problems include simple bounds on all the variables as well as general linear constraints. A feature of the proposed method is that it is able to exploit the structure of simple bound constraints. This allows the method to retain efficiency when the number ofgeneral constraints active at the solution is small. Furthermore, the efficiency of the method improves as the number of active bound constraints increases. This research was supported by the U.S. Department of Energy Contract DE-AC03-76SF00326, PA No. DE-AT03-76ER72018; National Science Foundation Grants MCS-7926009 and ECS-8012974; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-79-C-0110. The work of Nicholas Gould was supported by the Science and Engineering Research Council of Great Britain.     

A note on duality in disjunctive programming

We state a duality theorem for disjunctive programming, which generalizes to this class of problems the corresponding result for linear programming.This work was supported by the National Science Foundation under Grant No. MPS73-08534 A02 and by the US Office of Naval Research under Contract No. N00014-75-C-0621-NR047-048.     

A note on a sufficient-decrease criterion for a non-derivative step-length procedure

A step-length algorithm is an essential part of many descent methods for unconstrained and constrained optimization. In this note we present a criterion that defines an acceptable step length when only function values are available at trial step lengths.This research was supported by the U.S. Department of Energy Contract DE-AC03-76SF00326, PA No. DE-AT03-76ER72018; National Science Foundation Grants MCS-7926009 and ECS-8012974; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-79-C-0110.     

Least-index resolution of degeneracy in quadratic programming

In this study, we combine least-index pivot selection rules with Keller's algorithm for quadratic programming to obtain a finite method for processing degenerate problems.Research and reproduction of this report were partially supported by National Science Foundation Grant MCS76-81259; and the Office of Naval Research Contract N00014-75-C-0267.     

Effect of model uncertainty on some optimal routing problems

We study the effect of model uncertainties on optimal routing in a system of parallel queues. The uncertainty arises in modeling the service time distribution for the customers (jobs, packets) to be served. For a Poisson arrival process and Bernoulli routing, the optimal mean system delay generally depends on the variance of this distribution. However, as the input traffic load approaches the system capacity, the optimal routing assignment and corresponding mean system delay are shown to converge to a variance-invariant point. The implications of these results are examined in the context of gradient-based routing algorithms. An example of a model-independent algorithm using on-line gradient estimation is also included and its performance compared with that of model-based algorithms.This work was supported in part by the National Science Foundation under Grant ECS-88-01912, by the Office of Naval Research under Contract N00014-87-K-0304, and by NASA under Contract NAG 2-595.     

An alternative method for a global analysis of quadratic programs in a finite number of steps

This paper considers the global analysis of general quadratic programs in a finite number of steps. A procedure is presented for recursively finding either the global minimum or a halfline of the constraint set along which the minimand is unbounded below.Research was partially supported by the U.S. Energy Research and Development Administration Contract EY-76-S-03-0326 PA #18; the Office of Naval Research Contracts N00014-75-C-0267 and N00014-75-C-0865; and the National Science Foundation Grants MCS76-20019 and MCS76-81259.     

Low order polynomial bounds on the expected performance of local improvement algorithms

We present a general abstract model of local improvement, applicable to such diverse cases as principal pivoting methods for the linear complementarity problem and hill climbing in artificial intelligence. The model accurately predicts the behavior of the algorithms, and allows for a variety of probabilistic assumptions that permit degeneracy. Simulation indicates an approximately linear average number of iterations under a variety of probability assumptions. We derive theoretical bounds of 2en logn and en ² for different distributions, respectively, as well as polynomial bounds for a broad class of probability distributions. We conclude with a discussion of the applications of the model to LCP and linear programming.The author was supported by the New Faculty Research Development Program of the Georgia Institute of Technology. This work is based on the author's Ph.D. thesis, performed under George Dantzig at Stanford 1978–81, at the Systems Optimization Laboratory. While at Stanford, research was supported in part by Department of Energy Contract AM03-76SF00326, PA #DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267; National Science Foundation Grants MCS76-81259, MCS-7926009 and ECS-8012974; and Army Research Office Contract DAA29-79-C-0110. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Large-scale linearly constrained optimization

An algorithm for solving large-scale nonlinear programs with linear constraints is presented. The method combines efficient sparse-matrix techniques as in the revised simplex method with stable quasi-Newton methods for handling the nonlinearities. A general-purpose production code (MINOS) is described, along with computational experience on a wide variety of problems.This research was supported by the U.S. Office of Naval Research (Contract N00014-75-C-0267), the National Science Foundation (Grants MCS71-03341 A04, DCR75-04544), the U.S. Energy Research and Development Administration (Contract E(04-3)-326 PA #18), the Victoria University of Wellington, New Zealand, and the Department of Scientific and Industrial Research Wellington, New Zealand.     

Continuous approximation schemes for stochastic programs

One of the main methods for solving stochastic programs is approximation by discretizing the probability distribution. However, discretization may lose differentiability of expectational functionals. The complexity of discrete approximation schemes also increases exponentially as the dimension of the random vector increases. On the other hand, stochastic methods can solve stochastic programs with larger dimensions but their convergence is in the sense of probability one. In this paper, we study the differentiability property of stochastic two-stage programs and discuss continuous approximation methods for stochastic programs. We present several ways to calculate and estimate this derivative. We then design several continuous approximation schemes and study their convergence behavior and implementation. The methods include several types of truncation approximation, lower dimensional approximation and limited basis approximation.His work is supported by Office of Naval Research Grant N0014-86-K-0628 and the National Science Foundation under Grant ECS-8815101 and DDM-9215921.His work is supported by the Australian Research Council.     

Algorithmic equivalence in quadratic programming,I: A least-distance programming problem

It is demonstrated that Wolfe's algorithm for finding the point of smallest Euclidean norm in a given convex polytope generates the same sequence of feasible points as does the van de Panne-Whinstonsymmetric algorithm applied to the associated quadratic programming problem. Furthermore, it is shown how the latter algorithm may be simplified for application to problems of this type.This work was supported by the National Science Foundation, Grant No. MCS-71-03341-AO4, and by the Office of Naval Research, Contract No. N00014-75-C-0267.