A primal conical linear programming algorithm

This paper completes the treatment of the conical approach to linear programming, introducing a conical primal algorithm of linear programming. After some recalls and improvements of a previous paper dealing with such an approach, the algorithm is defined. A first convergence result is then proved, which, along with a series of lemmata, allows to prove that the algorithm terminates in a finite number of steps     

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 convergence proof for linear mean value cross decomposition

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition that eliminates the need for using the Benders or Dantzig-Wolfe master problem. It is a generalization of the Brown-Robinson method for a finite matrix game and can also be considered as a generalization of the Kornai-Liptak method. It is based on the subproblem phase in cross decomposition, where we iterate between the dual subproblem and the primal subproblem. As input to the dual subproblem we use the average of a part of all dual solutions of the primal subproblem, and as input to the primal subproblem we use the average of a part of all primal solutions of the dual subproblem. In this paper we give a new proof of convergence for this procedure. Previously convergence has only been shown for the application to a special separable case (which covers the Kornai-Liptak method), by showing equivalence to the Brown-Robinson method.     

Aggregation bounds in stochastic linear programming

Stochastic linear programs become extremely large and complex as additional uncertainties and possible future outcomes are included in their formulation. Row and column aggregation can significantly reduce this complexity, but the solutions of the aggregated problem only provide an approximation of the true solution. In this paper, error bounds on the value of the optimal solution of the original problem are obtained from the solution of the aggregated problem. These bounds apply for aggregation of both random variables and time periods.     

Cross decomposition for mixed integer programming

Many methods for solving mixed integer programming problems are based either on primal or on dual decomposition, which yield, respectively, a Benders decomposition algorithm and an implicit enumeration algorithm with bounds computed via Lagrangean relaxation. These methods exploit either the primal or the dual structure of the problem. We propose a new approach, cross decomposition, which allows exploiting simultaneously both structures. The development of the cross decomposition method captures profound relationships between primal and dual decomposition. It is shown that the more constraints can be included in the Langrangean relaxation (provided the duality gap remains zero), the fewer the Benders cuts one may expect to need. If the linear programming relaxation has no duality gap, only one Benders cut is needed to verify optimality.     

Optimality in transient markov chains and linear programming

It is shown how a discrete Markov programming problem can be transformed, using a linear program, into an equivalent problem from which the optimal decision rule can be trivially deduced. This transformation is applied to problems which have either transient probabilities or discounted costs.This research was supported by the National Research Council of Canada, Grant A7751.     

A decomposition algorithm for quadratic programming

A decomposition algorithm using Lemke's method is proposed for the solution of quadratic programming problems having possibly unbounded feasible regions. The feasible region for each master program is a generalized simplex of minimal size. This property is maintained by a dropping procedure which does not affect the finiteness of the convergence. The details of the matrix transformations associated with an efficient implementation of the algorithm are given. Encouraging preliminary computational experience is presented.     

Generalized capacities in linear programming

Within the framework of linear programming in paired spaces (Duffin, Kretschmer) we introduce quantities which are analogs of direct and adjoint capacity in potential theory (Ohtsuka), and we give conditions for these quantities to be equal     

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     

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

Polyhedral extensions of some theorems of linear programming

Three theorems of linear programming form our starting point: Tucker's theorem (1956) concerning the existence of optimal solutions satisfying the complementary slackness conditions strictly, and Williams' two theorems (1970) concerning the coordinatewise complementary behavior of feasible and optimal solutions. Here, we establish that the same phenomena hold in another, more versatile framework involving general polyhedral convexity. As one main application, the results are transferred into the context of the monotone complementarity problem. Several other theoretical applications are indicated.Research supported in part by the National Science Foundation under grant number MCS 79-05793 at the University of Illinois at Urbana-Champaign.     

A note on node aggregation and Benders' decomposition

Node aggregation methods have been previously studied as a means for approximating large scale transportation problems. In this paper, we show how the approximations inherent in Benders' decomposition method can be combined with node aggregation in optimizing large scale capacitated plant location problems. This research was supported by the National Science Foundation under Grant No. ECS-8117105.     

A nonlinear equation for linear programming

We present a characterization of the normal optimal solution of the linear program given in canonical form max{c ^tx: Ax = b, x 0}. (P) We show thatx ^* is the optimal solution of (P), of minimal norm, if and only if there exists anR > 0 such that, for eachr R, we havex ^* = (rc – A^t_r)₊. Thus, we can findx ^* by solving the following equation for _r A(rc – A^t_r)₊ = b. Moreover,(1/r) _r then converges to a solution of the dual program.On leave from The University of Alberta, Edmonton, Canada. Research partially supported by the National Science and Engineering Research Council of Canada.     

A primal—dual affine-scaling potential-reduction algorithm for linear programming

We propose a potential-reduction algorithm which always uses the primal—dual affine-scaling direction as a search direction. We choose a step size at each iteration of the algorithm such that the potential function does not increase, so that we can take a longer step size than the minimizing point of the potential function. We show that the algorithm is polynomial-time bounded. We also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

A dual perturbation view of linear programming

Solving standard-form linear prograrns via perturbation of the primal objective function has received much attention recently. In this paper, we investigate a new perturbation scheme which obtains a dual optimal solution by perturbing the dual feasible domain under different norms. A dual-to-primal conversion formula is also provided. We show that this new perturbation scheme actually generalizes the primal entropic perturbation approach to linear programming.Partially sponsored by the North Carolina Supercomputing Center 1994 Cray Research Grant and the National Textile Center Research Grant.     

Consistent aggregation of linear complementarity problems

Aggregating linear complementarity problems under a general definition of constrained consistency leads to the possibility of consistent aggregation of linear and quadratic programming models and bimatrix games. Under this formulation, consistent aggregation of dual variables is also achieved. Furthermore, the existence of multiple sets of aggregation operators is discussed and illustrated with a numerical example. Constrained consistency can also be interpreted as a disaggregation rule. This aspect of the problem may be important for implementing macro (economic) policies by means of micro (economic) agents.Giannini Foundation Paper No. 548.     

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.     

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.     

Linear programming in measure spaces

This paper studies a linear programming problem in measure spaces (LPM). Several results are obtained. First, the optimal value of LPM can be equal to the optimal value of the dual problem (DLPM), but the solution of DLPM may be not exist in its feasible region. Sccond, :he relations between the optimal solution of LPM and the extreme point of the feasible region of LPM are discussed. In order to investigate the conditions under which a feasible solution becomes an extremal point, the inequality constraint of LPM is transformed to an equality constraint. Third, the LPM can be reformulated to be a general capacity problem (GCAP) or a linear semi-infinite programming problem (LSIP = SIP), and under appropriate restrictioiis, the algorithm developed by the authors in [7] and [8] are applicable for developing an approximation scheme for the optimal solution of LPM     

Mixed-integer quadratic programming

This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a suitable approach for solving such programs. However, the program does not become more tractable if this method is used, since Benders' cuts are quadratic in the integer variables. A new equivalent formulation that renders the program tractable is developed, under which the dual objective function is linear in the integer variables and the dual constraint set is independent of these variables. Benders' cuts that are derived from the new formulation are linear in the integer variables, and the original problem is decomposed into a series of integer linear master problems and standard quadratic subproblems. The new formulation does not introduce new primary variables or new constraints into the computational steps of the decomposition algorithm.The author wishes to thank two anonymous referees for their helpful comments and suggestions for revising the paper.