Implicit representation of generalized variable upper bounds in linear programming

In certain linear programs, especially those derived from integer programs, large numbers of constraints may have very simple form. Examples are:x _ij 1 (simple upper bounds [SUB]), _i x _ij = 1 (generalized upper bounds [GUB]) andx _ij y _i (variable upper bounds [VUB]). A class of constraints called generalized VUB [GVUB] is introduced which includes GUB and VUB as special cases. Also introduced is a method for representing GVUB constraints implicitly within the mechanics of the simplex method.Research supported in part by the Mobil Oil Corporation.     

A note on Schrage's generalised variable upper bounds

An improved procedure for implementing pivoting, based upon ideas from generalised upper bounds, is suggested for Schrage's generalised variable upper bounds.     

Modifying the forrest-Tomlin and saunders updates for linear programming problems with variable upper bounds

The author previously described a modification of the simplex method to handle variable upper bounds implicitly. This method can easily be used when the representation of the basis inverse (e.g. a triangular decomposition of the basis) is maintained as a dense matrix in core, but appears to cause difficulties for large problems where secondary storage and packed matrices may be employed. Here we show how the Fonest—Tomlin and Saunders updating schemes, which are designed for such large problems, can be adapted. Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS82-15361.     

Modifying the forrest-tomlin and saunders updates for linear programming problems with variable upper bounds

The author previously described a modification of the simplex method to handle variable upper bounds implicitly. This method can easily be used when the representation of the basis inverse (e.g. a triangular decomposition of the basis) is maintained as a dense matrix in core, but appears to cause difficulties for large problems where secondary storage and packed matrices may be employed. Here we show how the Forrest-Tomlin and Saunders updating schemes, which are designed for such large problems, can be adapted.Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS82-15361.     

A degeneracy exploiting LU factorization for the simplex method

For general sparse linear programs two of the most efficient implementations of the LU factorization with Bartels—Golub updating are due to Reid and Saunders. This paper presents an alternative approach which achieves fast execution times for degenerate simplex method iterations, especially when used with multiple pricing. The method should have wide applicability since the simplex method performs a high proportion of degenerate iterations on most practical problems. A key feature of Saunders' method is combined with the updating strategy of Reid so as to make the scheme suitable for implementation out of core. Its efficiency is confirmed by experimental results.     

A bump triangular dynamic factorization algorithm for the simplex method

A dynamic factorization algorithm is developed which algebraically partitions the basis inverse in such a manner so that the simplex method can be executed from a series of small inverses and the basis itself. This partition is maintained dynamically so that the additional memory required to represent the basis inverse reduces to this series of small inverses for in-core implementations.The algorithm is intended for use in solving general large-scale linear programming problems. This new method of basis representation should permit rather large problems to be solved completely in-core.Preliminary computational experience is presented and comparisons are made with Reid's sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases. The computational experience indicated that a significant reduction in memory requirements can usually be obtained using the dynamic factorization approach with only a slight (up to about 20%) degradation of execution time.This research was supported in part by the Air Force Office of Scientific Research, Air Force System Command, USAF, under AFOSR Contract/Grant Number AFOSR-74-2715.     

Implicit representation of generalized variable upper bounds using the elimination form of the inverse on secondary storage

A constraint of a linear program is called a generalized variable upper bound (GVUB) constraint, if the right-hand is nonnegative and each variable with a positive coefficient in the constraint does not have a nonzero coefficient in any other GVUB constraint. Schrage has shown how to handle GVUB constraints implicitly in the simplex-method. It is demonstrated in this paper that the Forrest-Tomlin data structure may be used for the inverse of the working basis, and it is discussed how to update this representation from iteration to iteration.     

Extracting embedded generalized networks from linear programming problems

If a linear program (LP) possesses a large generalized network (GN) submatrix, this structure can be exploited to decrease solution time. The problems of finding maximum sets of GN constraints and finding maximum embedded GN submatrices are shown to be NP-complete, indicating that reliable, efficient solution of these problems is difficult. Therefore, efficient heuristic algorithms are developed for identifying such structure and are tested on a selection of twenty-three real-world problems. The best of four algorithms for identifying GN constraint sets finds a set which is maximum in twelve cases and averages 99.1% of maximum. On average, the GN constraints identified comprise more than 62.3% of the total constraints in these problems. The algorithm for identifying embedded GN submatrices finds submatrices whose sizes, rows plus columns, average 96.8% of an LP upper bound. Over 91.3% of the total constraint matrix was identified as a GN submatrix in these problems, on average.The act of being wise is the act of knowing what to overlook.William James (ca. 1890)     

An inexact approach to solving linear semi-infinite programming problems

In this paper, we propose an “inexact solution” approach to deal with linear semi-infinite programming problems with finitely many variables and infinitely many constraints over a compact metric space. A general convergence proof with some numerical examples are given and the advantages of using this approach are discussed     

On the average number of steps of the simplex method of linear programming

The goal is to give some theoretical explanation for the efficiency of the simplex method of George Dantzig. Fixing the number of constraints and using Dantzig's self-dual parametric algorithm, we show that the number of pivots required to solve a linear programming problem grows in proportion to the number of variables on the average. Supported in part by NSF Grant #MCS-8102262.     

Error bounds for the aggregated convex programming problem

Applied mathematical programming problems are often approximations of larger, more detailed problems. One criterion to evaluate an approximating program is the magnitude of the difference between the optimal objective values of the original and the approximating program. The approximation we consider is variable aggregation in a convex program. Bounds are derived on the difference between the two optimal objective values. Previous results of Geoffrion and Zipkin are obtained by specializing our results to linear programming. Also, we apply our bounds to a convex transportation problem. Thanks are due to Ron Dembo, Paul Zipkin and the referees for valuable comments. This research was supported by NSF Grant ENG-76-15599.     

On the role of bounds in stochastic linear programming

Stochastic linear programming (SLP) models involve multivariate integrals. Although in the discretely distributed case these integrals become sums they typically contain a large amount of terms. The purpose of this paper is twofold:On the one hand we discuss the usage of bounds concerning integrals for constructing SLP algorithms and secondly we point out the role of bounds-based algorithms for solving SLP problems. The conceptual considerations are demonstrated in the last section by computational results. The tests have been carried out by utilizing SLP-IOR, our model management system for SLP     

Modifications and implementation of the ellipsoid algorithm for linear programming

We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAG29-77-G-0114 and the National Science Foundation under Grant MCS-8006065.The work of this author was supported in part by the National Science Foundation under Grant ECS-7921279.     

A construction method in parametric programming

We consider a linear programming problem, with two parameters in the objective function, and present an algorithm for finding the decomposition of the parameter space into maximal polyhedral areas in which particular basic solutions are optimal. Special attention is paid to fill up areas of degenerate solutions.     

An effective linear approximation method for separable programming problems

Among the numerous applications of piecewise linearization methods include data fitting, network analysis, logistics, and statistics. In the early 1950s, a concave function was found to be able to be linearized by introducing 0-1 variables. Most textbooks in Operations Research offer such methods for expressing linear approximations. Various methods of linearization have also been developed in recent literature. Nevertheless, the transformed linear scheme has a severe shortcoming: most standard procedures for linearizing typically involve a large increase in the number of binary variables. Consequently, the gains to be derived from dealing with linear functions are quite likely to be nullified by the increase in the size of the problem.Conventional methods for linearizing a concave function with m break points require m-1 binary variables. However, when m becomes large, the computation will be very time-consuming and may cause a heavy computational burden.This study proposes an effective approach in which only ⌈log₂(m-1)⌉ binary variables are used. The proposed method has the following features: (i) it offers more convenient and efficient means of expressing a piecewise linear function; (ii) fewer 0-1 variables are used; (iii) the computational results show that the proposed method is much more efficient and faster than the conventional one, especially when the number of break points becomes large.     

Convergence of the cyclical relaxation method for linear inequalities

The relaxation method for linear inequalities is studied and new bounds on convergence obtained. An asymptotically tight estimate is given for the case when the inequalities are processed in a cyclical order. An improvement of the estimate by an order of magnitude takes place if strong underrelaxation is used. Bounds on convergence usually involve the so-called condition number of a system of linear inequalities, which we estimate in terms of their coefficient matrix. Paper presented at the XI. International Symposium on Mathematical Programming, Bonn, August 23–27, 1982.     

An implementation of Karmarkar's algorithm for linear programming

This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0.     

An algorithm for the linear complementarity problem with upper and lower bounds

In this paper, we adapt the octahedral simplicial algorithm for solving systems of nonlinear equations to solve the linear complementarity problem with upper and lower bounds. The proposed algorithm generates a piecewise linear path from an arbitrarily chosen pointz ⁰ to a solution point. This path is followed by linear programming pivot steps in a system ofn linear equations, wheren is the size of the problem. The starting pointz ⁰ is left in the direction of one of the 2 ⁿ vertices of the feasible region. The ray along whichz ⁰ is left depends on the sign pattern of the function value atz ⁰. The sign pattern of the linear function and the location of the points in comparison withz ⁰ completely govern the path of the algorithm.This research is part of the VF-Program Equilibrium and Disequilibrium in Demand and Supply, approved by the Netherlands Ministry of Education, Den Haag, The Netherlands.     

Eliminating columns in the simplex method for linear programming

We propose a column-eliminating technique for the simplex method of linear programming. A pricing criterion is developed for checking whether a dual hyperplane corresponding to a column intersects a simplex containing all of the optimal dual feasible solutions. If the dual hyperplane has no intersection with this simplex, we can eliminate the corresponding column from further computation during the course of the simplex method.The author is grateful for many discussions with Professor G. B. Dantzig, Stanford University, and for his valuable suggestions about this work. The author also gratefully acknowledges the editor and two referees for their very helpful comments, corrections, and remarks.     

An extension of the simplex algorithm for semi-infinite linear programming

We present a primal method for the solution of the semi-infinite linear programming problem with constraint index setS. We begin with a detailed treatment of the case whenS is a closed line interval in . A characterization of the extreme points of the feasible set is given, together with a purification algorithm which constructs an extreme point from any initial feasible solution. The set of points inS where the constraints are active is crucial to the development we give. In the non-degenerate case, the descent step for the new algorithm takes one of two forms: either an active point is dropped, or an active point is perturbed to the left or right. We also discuss the form of the algorithm when the extreme point solution is degenerate, and in the general case when the constraint index set lies in ^p . The method has associated with it some numerical difficulties which are at present unresolved. Hence it is primarily of interest in the theoretical context of infinite-dimensional extensions of the simplex algorithm.