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.     

New efficient shortest path simplex algorithm: pseudo permanent labels instead of permanent labels

We introduce a new network simplex pivot rule for the shortest path simplex algorithm. This new pivot rule chooses a subset of non-basic arcs to simultaneously enter into the basis. We call this operation a multiple pivot. We show that a shortest path simplex algorithm with this pivot rule performs O(n) multiple pivots and runs in O(nm) time. Our pivot rule is based on the new concept of a pseudo permanently labeled node, and it can be adapted to design a new label-correcting algorithm that runs in O(nm). Moreover, this concept lets us introduce new rules to identify negative cycles. Finally, we compare the network simplex algorithm with multiple pivots with other previously proposed efficient network simplex algorithm in a computational experiment.     

The double pivot simplex method

The simplex method, created by George Dantzig, optimally solves a linear program by pivoting. Dantzig’s pivots move from a basic feasible solution to a different basic feasible solution by exchanging exactly one basic variable with a nonbasic variable. This paper introduces the double pivot simplex method, which can transition between basic feasible solutions using two variables instead of one. Double pivots are performed by identifying the optimal basis in a two variable linear program using a new method called the slope algorithm. The slope algorithm is fast and allows an iteration of DPSM to have the same theoretical running time as an iteration of the simplex method. Computational experiments demonstrate that DPSM decreases the average number of pivots by approximately 41% on a small set of benchmark instances.     

Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

We show that a particular pivoting algorithm, which we call the lexicographic Lemke algorithm, takes an expected number of steps that is bounded by a quadratic inn, when applied to a random linear complementarity problem of dimensionn. We present two probabilistic models, both requiring some nondegeneracy and sign-invariance properties. The second distribution is concerned with linear complementarity problems that arise from linear programming. In this case we give bounds that are quadratic in the smaller of the two dimensions of the linear programming problem, and independent of the larger. Similar results have been obtained by Adler and Megiddo.Research partially funded by a fellowship from the Alfred Sloan Foundation and by NSF Grant ECS82-15361.     

Integration over a simplex,truncated cubes,and Eulerian numbers

Summary A method of integrating a function over a simplex is described in which (i) the simplex is first transformed into a right-angled isosceles simplex; (ii) this simplex is dissected into small cubes and truncated cubes; (iii) the integration over the truncated cubes is performed by the centroid method or by Stroud's method, and this requires the use of formulae for the moments of a truncated cube. These formulae are developed and are expressed in terms of Eulerian numbers. In the special case when the truncated cube is itself a right-angled isoceles simplex a new algorithm is given, depending on the discrete Fourier transform, for calculating the moments as polynomials inn wheren is the dimensionality.     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming

 We establish a precise correspondence between lift-and-project cuts for mixed 0-1 programs, simple disjunctive cuts (intersection cuts) and mixed-integer Gomory cuts. The correspondence maps members of one family onto members of the others. It also maps bases of the higher-dimensional cut generating linear program (CGLP) into bases of the linear programming relaxation. It provides new bounds on the number of facets of the elementary closure, and on the rank, of the standard linear programming relaxation of the mixed 0-1 polyhedron with respect to the above families of cutting planes. Based on the above correspondence, we develop an algorithm that solves (CGLP) without explicitly constructing it, by mimicking the pivoting steps of the higher dimensional (CGLP) simplex tableau by certain pivoting steps in the lower dimensional (LP) simplex tableau. In particular, we show how to calculate the reduced costs of the big tableau from the entries of the small tableau and based on this, how to identify a pivot in the small tableau that corresponds to one or several improving pivots in the big tableau. The overall effect is a much improved lift-and-project cut generating procedure, which can also be interpreted as an algorithm for a systematic improvement of mixed integer Gomory cuts from the small tableau. Received: October 5, 2000 / Accepted: March 19, 2002 Published online: September 5, 2002 Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through contract N00014-97-1-0196.     

On cycling in the network simplex method

There are well-known examples of cycling in the linear programming simplex method having basis size two and requiring only six pivots. We prove that any example having basis size two for the network simplex method requires at least ten pivots. We also present an example that achieves this lower bound. In addition, we show that an attractive variant of Cunningham's noncyling method does admit cycling.     

Sensitivity analysis in fuzzy number linear programming problems

In this paper, we generalize the concept of sensitivity analysis in fuzzy number linear programming (FLNP) problems by applying fuzzy simplex algorithms and using the general linear ranking functions on fuzzy numbers. The purpose of sensitivity analysis is to determine changes in the optimal solution of FNLP problem resulting from changes in the data. If the change affects the optimality of the basis, we perform primal pivots to achieve optimality by use of the fuzzy primal simplex method. Whenever the change destroys the feasibility of the optimal basis, we perform dual pivots to achieve feasibility by use of the fuzzy dual simplex method.     

On strongly polynomial dual simplex algorithms for the maximum flow problem

Several pivot rules for the dual network simplex algorithm that enable it to solve a maximum flow problem on ann-node,m-arc network in at most 2nm pivots and O(n ² m) time are presented. These rules are based on the concept of apreflow and depend upon the use of node labels which are either the lengths of a shortestpseudoaugmenting path from those nodes to the sink node orvalid underestimates of those lengths. Extended versions of our algorithms are shown to solve an important class of parametric maximum flow problems with no increase in the worst-case pivot and time bounds of these algorithms. This research was supported in part by NSF Grants DMS 91-06195, DMS 94-14438, and CDR 84-21402 and DOE Grant DE-FG02-92ER25126.     

The Klee–Minty random edge chain moves with linear speed

An infinite sequence of 0's and 1's evolves by flipping each 1 to a 0 exponentially at rate 1. When a 1 flips, all bits to its right also flip. Starting from any configuration with finitely many 1's to the left of the origin, we show that the leftmost 1 moves right with bounded speed. Upper and lower bounds are given on the speed. A consequence is that a lower bound for the run time of the random‐edge simplex algorithm on a Klee–Minty cube is improved so as to be quadratic, in agreement with the upper bound. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Solving Bilevel Linear Programs Using Multiple Objective Linear Programming

We present an algorithm for solving bilevel linear programs that uses simplex pivots on an expanded tableau. The algorithm uses the relationship between multiple objective linear programs and bilevel linear programs along with results for minimizing a linear objective over the efficient set for a multiple objective problem. Results in multiple objective programming needed are presented. We report computational experience demonstrating that this approach is more effective than a standard branch-and-bound algorithm when the number of leader variables is small.     

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.     

Improved semidefinite bounding procedure for solving Max-Cut problems to optimality

We present an improved algorithm for finding exact solutions to Max-Cut and the related binary quadratic programming problem, both classic problems of combinatorial optimization. The algorithm uses a branch-(and-cut-)and-bound paradigm, using standard valid inequalities and nonstandard semidefinite bounds. More specifically, we add a quadratic regularization term to the strengthened semidefinite relaxation in order to use a quasi-Newton method to compute the bounds. The ratio of the tightness of the bounds to the time required to compute them depends on two real parameters; we show how adjusting these parameters and the set of strengthening inequalities gives us a very efficient bounding procedure. Embedding our bounding procedure in a generic branch-and-bound platform, we get a competitive algorithm: extensive experiments show that our algorithm dominates the best existing method.     

A simple,all primal branch and bound approach to pure and mixed integer binary programs

Many branch and bound procedures for integer programming employ linear programming to obtain bound information. Nodes in the tree structure are defined by explicitly changing bounds on certain variables and/or adding one or more constraints to the parent LP; thus, primal feasibility is destroyed. The design and analysis of the resulting tree structure requires that basis information be stored for each node and that feasibility restoring pivots be used to obtain the node bound. In turn, this may require the introduction of artificial variables and/or dual simplex pivots.This paper describes a simple procedure for branch and bound that does not destroy primal feasibility. Moreover, the information required to be stored to define the node problems is minimal.     

On linear programs with random costs

We consider linear programs in which the objective function (cost) coefficients are independent non-negative random variables, and give upper bounds for the random minimum cost. One application shows that for quadratic assignment problems with such costs certain branch-and-bound algorithms usually take more than exponential time.     

A branch-and-bound algorithm for instrumental variable quantile regression

This paper studies a statistical problem called instrumental variable quantile regression (IVQR). We model IVQR as a convex quadratic program with complementarity constraints and—although this type of program is generally NP-hard—we develop a branch-and-bound algorithm to solve it globally. We also derive bounds on key variables in the problem, which are valid asymptotically for increasing sample size. We compare our method with two well known global solvers, one of which requires the computed bounds. On random instances, our algorithm performs well in terms of both speed and robustness.     

Some generalizations of the criss-cross method for quadratic programming

Three generalizations of the criss-cross method for quadratic programming are presented here. Tucker’s, Cottle’s and Dantzig’s principal pivoting methods are specialized as diagonal and exchange pivots for the linear complementarity problem obtained from a convex quadratic program

A finite criss-cross method, based on least-index resolution, is constructed for solving the LCP. In proving finiteness, orthogonality properties of pivot tableaus and positive semidefiniteness of quadratic matrices are used

In the last section some special cases and two further variants of the quadratic criss-cross method are discussed. If the matrix of the LCP has full rank, then a surprisingly simple algorithm follows, which coincides with Murty’s ‘Bard type schema’ in the P matrix case     

Quadratic model for allocating operational budget in public and nonprofit organizations

We develop a quadratic model for allocating operational budgets in public and nonprofit organizations. The allocations for each organizational unit have lower and upper bounds. The objective function is to minimize the weighted sum of the quadratic deviations of each allocation from its bounds. The optimal allocations are mostly around the midpoint between the bounds. A simple algorithm is presented to derive the solution. The new quadratic model is compared to the familiar linear model for budget allocation, which almost always, provides extreme allocations on the bounds: for some units on the upper bound, while for others, on the lower bound. We perform sensitivity analyses, and resolve special cases of the model with closed form solution. Moreover, we show various properties of the quadratic budget allocation model and prove that its fairness index is higher than that of the linear model. The model, with its variants, was actually used for allocating budgets in various university setups; some examples are presented here.