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 staircase linear programs by the simplex method, 1: Inversion

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or staircase, structure. The present paper looks at inversion routines within the simplex method, particularly those for sparse triangular factorization of a basis by Gaussian elimination and for solution of triangular linear systems. The succeeding paper examines pricing routines. Both papers describe extensive (though preliminary) computational experience, and can point to some quite promising results.     

Solving staircase linear programs by the simplex method, 2: Pricing

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or ‘staircase’, structure. The preceding paper considered ‘inversion’ routines that factorize the basis and solve linear systems. The present paper examines ‘pricing’ routines that compute reduced costs for nonbasic variables and that select a variable to enter the basis at each iteration. Both papers describe extensive (although preliminary) computer experiments, and can point to some quite promising results. For pricing in particular, staircase computation strategies appear to offer modest but consistent savings; staircase selection strategies, properly chosen, may offer substantial savings in number of iterations, time per iteration, or both.     

An unconstrained convex programming view of linear programming

The major interest of this paper is to show that, at least in theory, a pair of primal and dual -optimal solutions to a general linear program in Karmarkar's standard form can be obtained by solving an unconstrained convex program. Hence unconstrained convex optimization methods are suggested to be carefully reviewed for this purpose.     

An algorithm for computing equilibria in a linear monetary economy

An algorithm is presented for computing equilibria in a linear monetary economy, that is, an exchange economy in which all individuals have linear utility functions and in which goods are bought and sold only in exchange for money. The algorithm computes the equilibrium prices by solving a finite sequence of linear programming problems.     

Finding an interior point in the optimal face of linear programs

We study the problem of finding a point in the relative interior of the optimal face of a linear program. We prove that in the worst case such a point can be obtained in O(n ³ L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linear programming problems in the NETLIB test set.Research supported in part by NSF Grant CCR-8810107, CCR-9019469 and a grant from GTE Laboratories.Research supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615 through Rice University.     

Load balancing in the parallel optimization of block-angular linear programs

Decomposition algorithms for block-angular linear programs give rise to a natural, coarse-grained parallelism that can be exploited by processing the subproblems concurrently within a distributed-memory environment. The parallel efficiency of the distributed approach, however, is critically dependent on the duration of the inherently serial master phase relative to that of the bottleneck subproblem. This paper investigates strategies for improving efficiency in distributed Dantzig—Wolfe decomposition by better balancing the load between the master and subproblem processors. We report computational experience on an Intel iPSC/2 hypercube multiprocessor with test problems having dimensions up to about 30 000 rows, 87 000 columns, and 200 coupling constraints.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases

We describe a sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases. It includes interchanges that, whenever this is possible, avoid the use of any eliminations (with consequent fill-ins) when revising the factorization at an iteration. Test results on some medium scale problems are presented and comparisons made with the algorithm of Forrest and Tomlin.     

A parametric linear complementarity technique for the computation of equilibrium prices in a single commodity spatial model

This paper presents a parametric linear complementarity technique for the computation of equilibrium prices in a single commodity spatial model. We first reformulate the model as a linear complementarity problem and then apply the parametric principal pivoting algorithm for its solution. This reformulation leads to the study of an arc—arc weighted adjacency matrix associated with a simple digraph having weights on the nodes. Several basic properties of such a matrix are derived. Using these properties, we show how the parametric principal pivoting algorithm can be greatly simplified in this application. Finally, we report some computational experience with the proposed technique for solving some large problems.     

Feasibility issues in a primal-dual interior-point method for linear programming

A new method for obtaining an initial feasible interior-point solution to a linear program is presented. This method avoids the use of a big-M, and is shown to work well on a standard set of test problems. Conditions are developed for obtaining a near-optimal solution that is feasible for an associated problem, and details of the computational testing are presented. Other issues related to obtaining and maintaining accurate feasible solutions to linear programs with an interior-point method are discussed. These issues are important to consider when solving problems that have no primal or dual interior-point feasible solutions.     

Computation of M. L. estimates for the parameters of a negative binomial distribution from grouped data. A comparison of the scoring,Newton—Raphson and E-M algorithms

Computation of M. L. estimates for the parameters of a negative binomial distribution from grouped data is considered. For this problem the Scoring, Newton—Raphson and E-M algorithm is derived. Using simulated data the performance of the algorithms is compared with respect to convergence, number of iterations and computing time. Finally an empirical example drawn from actuarial science is given.     

Combining phase I and phase II in a potential reduction algorithm for linear programming

This paper describes an affine potential reduction algorithm for linear programming that simultaneously seeks feasibility and optimality. The algorithm is closely related to a similar method of Anstreicher. The new features are that we use a two-dimensional programming problem to derive better lower bounds than Anstreicher, that our direction-finding subproblem treats phase I and phase II more symmetrically, and that we do not need an initial lower bound. Our method also allows for the generation of a feasible solution (so that phase I is terminated) during the course of the iterations, and we describe two ways to encourage this behavior.Research supported in part by NSF grant DMS-8904406 and by NSF, AFOSR and ONR through NSF grant DMS-8920550.