Revised dantzig-wolfe decomposition for staircase-structured linear programs

Staircase structured linear programs arise naturally in the study of engineering economic systems. One general approach to solving such LP's is the technique of nested decomposition of the primal or dual problem. The research described in this paper proposes a revised decomposition algorithm that incorporates knowledge of the structure of the staircase basis in forming the decomposed linear programs. Column proposals from the revised subproblems are shown to achieve maximum penetration against the master problem basis. The proposed algorithm resorts to the regular Dantzig-Wolfe subproblem to test for optimality. The algorithm is shown to be finite and is compared to the Abrahamson-Wittrock algorithm. Computational results indicate substantial improvement over the Dantzig-Wolfe algorithm in most cases. A numerical example of the algorithm is provide in the appendix. This research was supported by National Science Foundation grant ECS-8106455 to Cornell University.     

Mslip: A computer code for the multistage stochastic linear programming problem

This paper describes an efficient implementation of a nested decomposition algorithm for the multistage stochastic linear programming problem. Many of the computational tricks developed for deterministic staircase problems are adapted to the stochastic setting and their effect on computation times is investigated. The computer code supports an arbitrary number of time periods and various types of random structures for the input data. Numerical results compare the performance of the algorithm to MINOS 5.0.     

Decomposition of linear programs using parallel computation

This paper describes DECOMPAR: an implementation of the Dantzig-Wolfe decomposition algorithm for block-angular linear programs using parallel processing of the subproblems. The software is based on a robust experimental code for LP decomposition and runs on the CRYSTAL multicomputer at the University of Wisconsin-Madison. Initial computational experience is reported. Promising directions in future development of this approach are discussed.Research supported in part by the Office of Naval Research under grant N00014-87-K-0163.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

On the optimal value function for certain linear programs with unbounded optimal solution sets

Often, the coefficients of a linear programming problem represent estimates of true values of data or are subject to systematic variations. In such cases, it is useful to perturb the original data and to either compute, estimate, or otherwise describe the values of the functionf which gives the optimal value of the linear program for each perturbation. If the right-hand derivative off at a chosen point exists and is calculated, then the values off in a neighborhood of that point can be estimated. However, if the optimal solution set of either the primal problem or the dual problem is unbounded, then this derivative may not exist. In this note, we show that, frequently, even if the primal problem or the dual problem has an unbounded optimal solution set, the nature of the values off at points near a given point can be investigated. To illustrate the potential utility of our results, their application to two types of problems is also explained.This research was supported, in part, by the Center for Econometrics and Decision Sciences, University of Florida, Gainesville, Florida.The author would like to thank two anonymous reviewers for their most useful comments on earlier versions of this paper.     

Nested decomposition of multistage nonlinear programs with recourse

Nested decomposition is extended to the case of arborescent nonlinear programs. Duals of extensive forms of nonlinear multistage stochastic programs constitute a particular class of those problems; the method is tested on a set of problems of that type.     

A preliminary set of applications leading to stochastic semidefinite programs and chance-constrained semidefinite programs

Ariyawansa and Zhu have recently introduced (two-stage) stochastic semidefinite programs (with recourse) (SSDPs) [1] and chance-constrained semidefinite programs (CCSDPs) [2] as paradigms for dealing with uncertainty in applications leading to semidefinite programs. Semidefinite programs have been the subject of intense research during the past 15 years, and one of the reasons for this research activity is the novelty and variety of applications of semidefinite programs. This research activity has produced, among other things, efficient interior point algorithms for semidefinite programs. Semidefinite programs however are defined using deterministic data while uncertainty is naturally present in applications. The definitions of SSDPs and CCSDPs in [1] and [2] were formulated with the expectation that they would enhance optimization modeling in applications that lead to semidefinite programs by providing ways to handle uncertainty in data. In this paper, we present results of our attempts to create SSDP and CCSDP models in four such applications. Our results are promising and we hope that the applications presented in this paper would encourage researchers to consider SSDP and CCSDP as new paradigms for stochastic optimization when they formulate optimization models.     

A barrier method for dynamic Leontief-type linear programs

In this paper, we specialize Gill et al.'s projected Newton barrier method to solve a large-scale linear program of dynamic (i.e. multistage) Leontief-type constraints. We propose an efficient and stable method for solving the least-squares subproblems, the crucial part of the barrier method. The key step is to exploit a special structure of the constraint matrix and reduce the matrix of the normal equation for the least-squares problem to a banded matrix. By comparing the average-case operations count of this specialized barrier method with that of the sparse simplex method, we show that this method performs at least O(T) faster than the simplex method for such stype of linear programs, where T is the number of time periods (i.e. stages).     

Convergence behavior of decomposition algorithms for linear programs

This paper discusses plausible explanations of the somewhat folkloric, ‘tailing off’ convergence behavior of the Dantzig-Wolfe decomposition algorithm for linear programs. Is is argued that such beahvior may be used to numerical inaccuracy. Procedures to identify and mitigate such difficulties are outlined.     

Solution of parametrized linear inequalities by Fourier elimination and its applications

The parametric solution of a linear system of inequalitiesAxBb, with parameterb, is considered. Fourier elimination is used to give a facial representation for the set ofb-values for which the system is consistent. Some interesting applications of the problem are discussed. Although the worst case complexity of the method is an exponential function of the size ofA, the computations are intuitive and very simple.     

A pathological case in the reduction of linear programs

This note discusses a pathological case which may arise when a reduction procedure is used to detect implied ‘free’ variables in linear programs. This is the possibility of a spurious unbounded condition. We detail the cause of this anomaly and discuss algorithmic remedies, giving computational experience.     

Postoptimality for multistage stochastic linear programs

The contamination technique is presented as a flexible and relatively easily tractable tool to postoptimality analysis for scenario based multistage stochastic linear programs. It is promising especially in cases when the influence of additional or out-of-sample scenarios on the already solved problem is to be explored.Research supported in part by the Grant Agency of the Czech Republic under Grant No. 402/93/0631.     

A procedure for one-parametric linear programming

A procedure is proposed for the parametric linear programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The solution vector and the optimum value are determined explicitly as rational functions of the parameter. In addition to standard linear programming technique, only the determination of eigenvalues is required. The procedure is compared to those by Dinkelbach and Zsigmond, and a numerical example is given.     

A constraint generation algorithm for large scale linear programs using multiple-points separation

In order to solve linear programs with a large number of constraints, constraint generation techniques are often used. In these algorithms, a relaxation of the formulation containing only a subset of the constraints is first solved. Then a separation procedure is called which adds to the relaxation any inequality of the formulation that is violated by the current solution. The process is iterated until no violated inequality can be found. In this paper, we present a separation procedure that uses several points to generate violated constraints. The complexity of this separation procedure and of some related problems is studied. Also, preliminary computational results about the advantages of using multiple-points separation procedures over traditional separation procedures are given for random linear programs and survivable network design. They illustrate that, for some specific families of linear programs, multiple-points separation can be computationally effective.     

Sensitivity method for basis inverse representation in multistage stochastic linear programming problems

A version of the simplex method for solving stochastic linear control problems is presented. The method uses a compact basis inverse representation that extensively exploits the original problem data and takes advantage of the supersparse structure of the problem. Computational experience indicates that the method is capable of solving large problems.This research was supported by Programs CPBP02.15 and RPI.02.     

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.     

An implementation of steepest-descent augmentation for linear programs

Generalizing the simplex method, circuit augmentation schemes for linear programs follow circuit directions through the interior of the underlying polyhedron. Steepest-descent augmentation is especially promising, but an implementation of the iterative scheme is a significant challenge. We work towards a viable implementation through a model in which a single linear program is updated dynamically to remain in memory throughout. Computational experiments exhibit dramatic improvements over a naïve approach and reveal insight into the next steps required for large-scale computations.