An advanced implementation of the Dantzig—Wolfe decomposition algorithm for linear programming

Since the original work of Dantzig and Wolfe in 1960, the idea of decomposition has persisted as an attractive approach to large-scale linear programming. However, empirical experience reported in the literature over the years has not been encouraging enough to stimulate practical application. Recent experiments indicate that much improvement is possible through advanced implementations and careful selection of computational strategies. This paper describes such an effort based on state-of-the-art, modular linear programming software (IBM's MPSX/370).     

Random linear programs with many variables and few constraints

We extend and simplify Smale's work on the expected number of pivots for a linear program with many variables and few constraints. Our analysis applies to new versions of the simplex algorithm and to new random distributions.     

A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs

We consider probabilistically constrained linear programs with general distributions for the uncertain parameters. These problems involve non-convex feasible sets. We develop a branch-and-bound algorithm that searches for a global optimal solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partition elements. This basic algorithm is enhanced by domain reduction and cutting plane strategies to reduce the size of the partition elements and hence tighten bounds. The proposed branch-reduce-cut algorithm exploits the monotonicity properties inherent in the problem, and requires solving linear programming subproblems. We provide convergence proofs for the algorithm. Some illustrative numerical results involving problems with discrete distributions are presented.     

On the nucleolus of NTU-games defined by multiple objective linear programs

In this article we derive a class of cooperative games with non-transferable utility from multiple objective linear programs. This is done in order to introduce the nucleolus, a solution concept from cooperative game theory, as a solution to multiple objective linear problems.We show that the nucleolus of such a game is a singleton, which is characterized by inclusion in the least core and the reduced game property. Furthermore the nucleolus satisfies efficiency, anonymity and strategic equivalence.We also present a polynomially bounded algorithm for computation of the nucleolus. Letn be the number of objective functions. The nucleolus is obtained by solving at most2n linear programs. Initially the ideal point is computed by solvingn linear programs. Then a sequence of at mostn linear programs is solved, and the nucleolus is obtained as the unique solution of the last program.Financial support from Nordic Academy for Advanced Study (NorFA) is gratefully acknowledged. Part of this work was done during autumn 1993 at Institute of Finance and Management Science, Norwegian School of Economics and Business Administration.     

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.     

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.     

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.     

Identification of special structure constraints in linear programs

In large LPs it may be that a major fraction of the constraints has a particularly simple form. Frequently this simple form may be exploited by either decomposition or implicit representation methods. In these cases, the effective size and computational difficulty are more closely related to the number of remaining nonspecial constraints than to the number of special constraints. A unified computational procedure is presented for mechanically identifying near maximal sets of special structure constraints for most of the kinds of special structures which have been identified thus far as being exploitable.     

Representing the space of linear programs as the Grassmann manifold

Each linear program (LP) has an optimal basis. The space of linear programs can be partitioned according to these bases, so called the basis partition. Discovering the structures of this partition is our goal. We represent the space of linear programs as the space of projection matrices, i.e., the Grassmann manifold. A dynamical system on the Grassmann manifold, first presented in Sonnevend et al. (Math Program 52:527–553), is used to characterize the basis partition as follows: From each projection matrix associated with an LP, the dynamical system defines a path and the path leads to an equilibrium projection matrix returning the optimal basis of the LP. We will present some basic properties of equilibrium points of the dynamical system and explicitly describe all eigenvalues and eigenvectors of the linearized dynamical system at equilibrium points. These properties will be used to determine the stability of equilibrium points and to investigate the basis partition. This paper is only a beginning of the research towards our goal. Research is supported in part by NUS Academic Research Grant R-146-000-084-112. The author wishes to thank Josef Stoer for his valuable comments on the paper and to thank Wingkeung To, Jie Wu, Xingwang Xu, Deqi Zhang and Chengbo Zhu for providing consultations on Differential Geometry and Grassmann manifolds and pointing out useful literature. The author is certainly responsible to all faults in the paper.     

A set of staircase linear programming test problems

A set of staircase linear programming test problems are made available for computational experiments.Research supported by the U.S. Department of Energy under contract DE-AC02-76CH00016.Research supported by the Belgian National Research Program in Energy, contract E/I/3.     

Bundle-based decomposition for large-scale convex optimization: Error estimate and application to block-angular linear programs

Robinson has proposed the bundle-based decomposition algorithm to solve a class of structured large-scale convex optimization problems. In this method, the original problem is transformed (by dualization) to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. In this paper, we give a posteriori error estimates on the approximate primal optimal solution and on the duality gap. We describe implementation and present computational experience with a special case of this class of problems, namely, block-angular linear programming problems. We observe that the method is efficient in obtaining the approximate optimal solution and compares favorably with MINOS and an advanced implementation of the Dantzig—Wolfe decomposition method.     

A new method for a class of linear variational inequalities

In this paper we introduce a new iterative scheme for the numerical solution of a class of linear variational inequalities. Each iteration of the method consists essentially only of a projection to a closed convex set and two matrix-vector multiplications. Both the method and the convergence proof are very simple.This work is supported by the National Natural Science Foundation of the P.R. China and NSF of Jiangsu.     

On the Glivenko-Cantelli problem in stochastic programming: Mixed-integer linear recourse

Expected recourse functions in linear two-stage stochastic programs with mixed-integer second stage are approximated by estimating the underlying probability distribution via empirical measures. Under mild conditions, almost sure uniform convergence of the empirical means to the original expected recourse function is established.     

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.     

A control parametrization algorithm for optimal control problems involving linear systems and linear 1

Computational schemes based on control parametrization techniques are known to be very efficient for solving optimal control problems. However, the convergence result is only available for the case in which the dynamic system is linear and without the terminal equality and inequality constraints. This paper is to improve this convergence result by allowing the presence of the linear terminal inequality. For illustration, an example arising in the study of optimally one-sided heating of a metal slab in a furnace is considered.     

Convergence of a cyclic ellipsoid algorithm for systems of linear equalities

A variable metric optimization method for non differentiable functions due to Shor, Yudin and Nemirovskii, and Khacian, is applied to a full rank system of linear equalities, under a cyclic implementation. At each step of the iteration, the variable metric matrix is used to construct an ellipsoid around the current iterate; this ellipsoid contains the solution. The variable metric matrix is updated in such a way that this inclusion property always hold, and that the volume of the ellipsoid shrinks as a geometric progression, whose rate depends only on the dimension of the space.For the problem of linear equalities, with cyclic implementation, it is shown that every axis of the ellipsoid shrinks more or less as a geometric progression (with the same rate for every axis) and thus that the distance between the iterates and the solution converges to zero as a geometric series whose rate depends only on the dimension of the space. The variable metric matrix is shown to build up information about the inverse of the matrix defining the system of equalities.A somewhat different implementation of the method is shown to converge in a number of steps equal at most to the dimension of the space.This research was supported in part by the D.G.E.S. (Quebec), the N.S.E.R.C. of Canada, under Grant A4152 and the S.S.H.R.C. of Canada.     

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.     

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).