A simplex algorithm for piecewise-linear programming II: Finiteness,feasibility and degeneracy

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. Part I of this paper has developed a general and direct simplex algorithm for piecewise-linear programming, under convenient assumptions that guarantee a finite number of basic solutions, existence of basic feasible solutions, and nondegeneracy of all such solutions. Part II now shows how these assumptions can be weakened so that they pose no obstacle to effective use of the piecewise-linear simplex algorithm. The theory of piecewise-linear programming is thereby extended, and numerous features of linear programming are generalized or are seen in a new light. An analysis of the algorithm's computational requirements and a survey of applications will be presented in Part III.This research has been supported in part by the National Science Foundation under grant DMS-8217261.     

A Dual Simplex Algorithm for Piecewise-Linear Programming

This paper presents a dual piecewise-linear simplex algorithm for minimizing convex separable piecewise-linear functions subject to linear constraints. It is an extension of Fourier's work on piecewise-linear programming to the dual piecewise-linear simplex algorithm. This algorithm has advantages over indirect methods which solve equivalent linear programs augmented by additional variables and/or constraints. Computational experience is presented which demonstrates the efficiency these advantages contribute.     

Piecewise-linear programming: The compact (CPLP) algorithm

A compact algorithm is presented for solving the convex piecewise-linear-programming problem, formulated by means of a separable convex piecewise-linear objective function (to be minimized) and a set of linear constraints. This algorithm consists of a finite sequence of cycles, derived from the simplex method, characteritic of linear programming, and the line search, characteristic of nonlinear programming. Both the required storage and amount of calculation are reduced with respect to the usual approach, based on a linear-programming formulation with an expanded tableau. The tableau dimensions arem×(n+1), wherem is the number of constraints andn the number of the (original) structural variables, and they do not increase with the number of breakpoints of the piecewise-linear terms constituting the objective function.     

A simplex algorithm for piecewise-linear programming III: Computational analysis and applications

The first two parts of this paper have developed a simplex algorithm for minimizing convex separable piecewise-linear functions subject to linear constraints. This concluding part argues that a direct piecewiselinear simplex implementation has inherent advantages over an indirect approach that relies on transformation to a linear program. The advantages are shown to be implicit in relationships between the linear and piecewise-linear algorithms, and to be independent of many details of implementation. Two sets of computational results serve to illustarate these arguments; the piecewise-linear simplex algorithm is observed to run 2–6 times faster than a comparable linear algorithm, not including any additional expense that might be incurred in setting up the equivalent linear program. Further support for the practical value of a good piecewise-linear programming algorithm is provided by a survey of many varied applications.This research has been supported in part by the National Science Foundation under grant DMS-8217261.     

Exploiting structure in piecewise-linear homotopy algorithms for solving equations

We consider the recent algorithms for computing fixed points or zeros of continuous functions fromR ⁿ to itself that are based on tracing piecewise-linear paths in triangulations. We investigate the possible savings that arise when these fixed-point algorithms with their usual triangulations are applied to computing zeros of functionsf with special structure:f is either piecewise-linear in certain variables, separable, or has Jacobian with small bandwidth. Each of these structures leads to a property we call modularity; the algorithmic path within a simplex can be continued into an adjacent simplex without a function evaluation or linear programming pivot. Modularity also arises without any special structure onf from the linearity of the function that is deformed tof. In the case thatf is separable we show that the path generated by Kojima's algorithm with the homotopyH ² coincides with the path generated by the standard restart algorithm of Merrill when the usual triangulations are employed. The extra function evaluations and linear programming steps required by the standard algorithm can be avoided by exploiting modularity.This research was performed while the author was visiting the Mathematics Research Center, University of Wisconsin-Madison, and was sponsored by the United States Army under Contract No. DAAG-29-75-C-0024 and by the National Science Foundation under Grant No. ENG76-08749.     

A penalty continuation method for the ∓∞ solution of overdetermined linear systems

A new algorithm for the ∓_∞ solution of overdetermined linear systems is given. The algorithm is based on the application of quadratic penalty functions to a primal linear programming formulation of the ∓_∞ problem. The minimizers of the quadratic penalty function generate piecewise-linear non-interior paths to the set of ∓_∞ solutions. It is shown that the entire set of ∓_∞ solutions is obtained from the paths for sufficiently small values of a scalar parameter. This leads to a finite penalty/continuation algorithm for ∓_∞ problems. The algorithm is implemented and extensively tested using random and function approximation problems. Comparisons with the Barrodale-Phillips simplex based algorithm and the more recent predictor-corrector primal-dual interior point algorithm are given. The results indicate that the new algorithm shows a promising performance on random (non-function approximation) problems.     

模糊线性规划问题的一种新的单纯形算法

提出求解模糊线性规划问题的一种新的思路 ,就是应用单纯形法先求解与 (FLP)相应的普通线性规划问题 ,通过模糊约束集与模糊目标集的隶属度的比较 ,获得两个集合交集的最优隶属度 ,将此最优隶属度代入最优单纯形表中 ,即可求得 (FLP)的解。本算法只需在一张适当的迭代表台上执行单纯形迭代过程 ,简捷方便适用     

Scaling,shifting and weighting in interior-point methods

We examine certain questions related to the choice of scaling, shifting and weighting strategies for interior-point methods for linear programming. One theme is the desire to make trajectories to be followed by algorithms into straight lines if possible to encourage fast convergence. While interior-point methods in general follow curves, this occurrence of straight lines seems appropriate to honor George Dantzig's contributions to linear programming, since his simplex method can be seen as following either a piecewise-linear path inn-space or a straight line inm-space (the simplex interpretation).Dedicated to Professor George B. Dantzig on the occasion of his eightieth birthday.Research supported in part by NSF, AFOSR, and ONR through NSF Grant DMS-8920550.     

A simplex algorithm for piecewise-linear fractional programming problems

Generalizations of the well-known simplex method for linear programming are available to solve the piecewise linear programming problem and the linear fractional programming problem. In this paper we consider a further generalization of the simplex method to solve piecewise linear fractional programming problems unifying the simplex method for linear programs, piecewise linear programs, and the linear fractional programs. Computational results are presented to obtain further insights into the behavior of the algorithm on random test problems.     

Linear programming via a quadratic penalty function

We use quadratic penalty functions along with some recent ideas from linearl ₁ estimation to arrive at a new characterization of primal optimal solutions in linear programs. The algorithmic implications of this analysis are studied, and a new, finite penalty algorithm for linear programming is designed. Preliminary computational results are presented.Research supported by grant No. 11-0505 from the Danish Natural Science Research Council SNF.     

Solving ℓ1 Regularization Problems With Piecewise Linear Losses

This article is concerned with the computational aspect of ?₁ regularization problems with a certain class of piecewise linear loss functions. The problem of computing the ?₁ regularization path for a piecewise linear loss can be formalized as a parametric linear programming problem. We propose an efficient implementation method of the parametric simplex algorithm for such a problem. We also conduct a simulation study to investigate the behavior of the number of “breakpoints” of the regularization path when both the number of observations and the number of explanatory variables vary. Our method is also applicable to the computation of the regularization path for a piecewise linear loss and the blockwise ?_∞ penalty. This article has supplementary material online.     

A hybrid approach to discrete mathematical programming

The dynamic programming and branch-and-bound approaches are combined to produce a hybrid algorithm for separable discrete mathematical programs. Linear programming is used in a novel way to compute bounds. Every simplex pivot permits a bounding test to be made on every active node in the search tree. Computational experience is reported.     

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 global quadratic algorithm for solving a system of mixed equalities and inequalities

A new algorithm is proposed which, under mild assumptions, generates a sequence{x _i } that starting at any point inR ⁿ will converge to a setX defined by a mixed system of equations and inequalities. Any iteration of the algorithm requires the solution of a linear programming problem with relatively few constraints. By only assuming that the functions involved are continuously differentiable a superlinear rate of convergence is achieved. No convexity whatsoever is required by the algorithm.     

An infeasible-interior-point predictor-corrector algorithm for theP *-geometric LCP

AP _*-geometric linear complementarity problem (P _*GP) as a generalization of the monotone geometric linear complementarity problem is introduced. In particular, it contains the monotone standard linear complementarity problem and the horizontal linear complementarity problem. Linear and quadratic programming problems can be expressed in a “natural” way (i.e., without any change of variables) asP _*GP. It is shown that the algorithm of Mizunoet al. [6] can be extended to solve theP _*GP. The extended algorithm is globally convergent and its computational complexity depends on the quality of the starting points. The algorithm is quadratically convergent for problems having a strictly complementary solution. The work of F. A. Potra was supported in part by NSF Grant DMS 9305760     

Multibody elastic contact analysis by quadratic programming

A quadratic programming method for contact problems is extended to a general problem involving contact ofn elastic bodies. Sharp results of quadratic programming theory provide an equivalence between the originaln-body contact problem and the simplex algorithm used to solve the quadratic programming problem. Two multibody examples are solved to illustrate the technique.     

Sign consistent linear programming problems

This article studies linear programming problems in which all minors of maximal order of the coefficient matrix have the same sign. We analyse the relationship between a special structure of the non-degenerate dual feasible bases of a linear programming problem and the structure of its associated matrix. In the particular case in which the matrix has all minors of each order k with the same strict sign ? _k , we provide a dual simplex revised method with good stability properties. In particular, this method can be applied to the totally positive linear programming problems, of great interest in many applications.     

Worst case behavior of the steepest edge simplex method

At each nondegenerate iteration of the steepest-edge simplex method one moves from a vertex of the polyhedron, P, of feasible points to an adjacent vertex along an edge that is steepest with respect to the linear objective function ψ. In this paper we show how to construct a sequence of linear programs (P_n,ψ_n) in n variables for which the number of iterations required by the steepest edge simplex method is 2ⁿ−1.     

The C 3 Theorem and a D 2 Algorithm for Large Scale Stochastic Mixed-Integer Programming: Set Convexification

This paper considers the two-stage stochastic integer programming problem, with an emphasis on instances in which integer variables appear in the second stage. Drawing heavily on the theory of disjunctive programming, we characterize convexifications of the second stage problem and develop a decomposition-based algorithm for the solution of such problems. In particular, we verify that problems with fixed recourse are characterized by scenario-dependent second stage convexifications that have a great deal in common. We refer to this characterization as the C³ (Common Cut Coefficients) Theorem. Based on the C³ Theorem, we develop a decomposition algorithm which we refer to as Disjunctive Decomposition (D²). In this new class of algorithms, we work with master and subproblems that result from convexifications of two coupled disjunctive programs. We show that when the second stage consists of 0-1 MILP problems, we can obtain accurate second stage objective function estimates after finitely many steps. This result implies the convergence of the D² algorithm.This research was funded by NSF grants DMII 9978780 and CISE 9975050.     

A o(n logn) algorithm for LP knapsacks with GUB constraints

A specialization of the dual simplex method is developed for solving the linear programming (LP) knapsack problem subject to generalized upper bound (GUB) constraints. The LP/GUB knapsack problem is of interest both for solving more general LP problems by the dual simplex method, and for applying surrogate constraint strategies to the solution of 0–1 Multiple Choice integer programming problems. We provide computational bounds for our method of o(n logn), wheren is the total number of problem variables. These bounds reduce the previous best estimate of the order of complexity of the LP/GUB knapsack problem (due to Witzgall) and provide connections to computational bounds for the ordinary knapsack problem.We further provide a variant of our method which has only slightly inferior worst case bounds, yet which is ideally suited to solving integer multiple choice problems due to its ability to post-optimize while retaining variables otherwise weeded out by convex dominance criteria.