Steepest-edge simplex algorithms for linear programming

We present several new steepest-edge simplex algorithms for solving linear programming problems, including variants of both the primal and the dual simplex method. These algorithms differ depending upon the space in which the problem is viewed as residing, and include variants in which this space varies dynamically. We present computational results comparing steepest-edge simplex algorithms and approximate versions of them against simplex algorithms that use standard pivoting rules on truly large-scale realworld linear programs with as many as tens of thousands of rows and columns. These results demonstrate unambiguously the superiority of steepest-edge pivot selection criteria to other pivot selection criteria in the simplex method.The research of this author was supported in part by NSF Grants DMS 85-12277, DMS 91-0619 and CDR 84-21402.     

Parametric linear programming and anti-cycling pivoting rules

The traditional perturbation (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore, restrict the choice of exiting basic variables. Bland's combinatorial pivoting rule also restricts the choice of exiting variables. Using ideas from parametric linear programming, we develop anticycling pivoting rules that do not limit the choice of exiting variables beyond the simplex ratio rule. That is, any variable that ties for the ratio rule can leave the basis. A similar approach gives pivoting rules for the dual simplex method that do not restrict the choice of entering variables.Supported in part by grant ECS-83-6224 from the Systems Theory and Operations Research Division of the National Science Foundation.Supported in part by Presidential Young Investigator grant 8451517-ECS of the National Science Foundation.     

The most-obtuse-angle row pivot rule for achieving dual feasibility: A computational study

We recently proposed several new pivot rules for achieving dual feasibility in linear programming, which are distinct from existing ones: the objective function value will no longer change necessarily monotonically in their solution process. In this paper, we report our further computational testing with one of them, the most-obtuse-angle rule. A two-phase dual simplex algorithm, in which the rule is used as a row selection rule for Phase-1, has been implemented in FORTRAN 77 modules, and was tested on a set of standard linear programming problems from NETLIB. We show that, if full pricing is applied, our code unambiguously will outperform MINOS 5.3, one of the best implementations of the simplex algorithm at present.     

Linear and quadratic programming in oriented matroids

We prove constructively duality theorems of linear and quadratic programming in the combinatorial setting of oriented matroids. One version of our algorithm for linear programing has the interesting feature of maintaining feasibility. The development of the quadratic programming duality result suggests the study of properties of square matrices such as symmetry and positive semi-definiteness in the context of oriented matroids.     

An exponential example for Terlaky's pivoting rule for the criss-cross simplex method

Recently T. Terlaky has proposed a new pivoting rule for the criss-cross simplex method for linear programming and he proved that his rule is convergent. In this note we show that the required number of iterations may be exponential in the number of variables and constraints of the problem.     

On simplex method with most-obtuse-angle rule and cosine rule

A class of simplex methods for solving linear programming (LP) problems, with cosine pivot rule, have been presented in some recent papers. In this paper we show that the cosine rule used in this class is equivalent to the most-obtuse-angle pivot rule, proposed by Pan (1990) [6]. The relation between the direct method for LP and the most-obtuse-angle rule is discussed.     

Pivot rules for linear programming: A survey on recent theoretical developments

The purpose of this paper is to discuss the various pivot rules of the simplex method and its variants that have been developed in the last two decades, starting from the appearance of the minimal index rule of Bland. We are mainly concerned with finiteness properties of simplex type pivot rules. Well known classical results concerning the simplex method are not considered in this survey, but the connection between the new pivot methods and the classical ones, if there is any, is discussed.In this paper we discuss three classes of recently developed pivot rules for linear programming. The first and largest class is the class of essentially combinatorial pivot rules including minimal index type rules and recursive rules. These rules only use labeling and signs of the variables. The second class contains those pivot rules which can actually be considered as variants or generalizations or specializations of Lemke's method, and so they are closely related to parametric programming. The last class has the common feature that the rules all have close connections to certain interior point methods. Finally, we mention some open problems for future research.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2115.     

The s-monotone index selection rules for pivot algorithms of linear programming

In this paper we introduce the concept of s-monotone index selection rule for linear programming problems. We show that several known anti-cycling pivot rules like the minimal index, Last-In–First-Out and the most-often-selected-variable pivot rules are s-monotone index selection rules. Furthermore, we show a possible way to define new s-monotone pivot rules. We prove that several known algorithms like the primal (dual) simplex, MBU-simplex algorithms and criss-cross algorithm with s-monotone pivot rules are finite methods.     

Degeneracy Subgraph of the Lemke Complementary Pivot Algorithm and Anticycling Rule

In this paper, we use the theory of degeneracy graphs recently developed by Gal et al. to introduce a graph for studying the adjacency of almost complementary feasible bases, some of which may be degenerate, which are of interest in the context of the linear complementarity problem. We study the structure of this graph with particular reference to the possibility of cycling and various anticycling rules in the Lemke complementary pivoting algorithm. We consider the transition node pivot rule introduced by Geue and show that this rule helps in avoiding cycling in the Lemke complementary pivoting algorithm under a suitable assumption.     

Combinatorial characterizations of K-matrices

e present a number of combinatorial characterizations of K-matrices. This extends a theorem of Fiedler and Pták on linear-algebraic characterizations of K-matrices to the setting of oriented matroids. Our proof is elementary and simplifies the original proof substantially by exploiting the duality of oriented matroids. As an application, we show that any simple principal pivot method applied to the linear complementarity problems with K-matrices converges very quickly, by a purely combinatorial argument.     

Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules

Abstract

Several variations of index selection rules for simplex-type algorithms for linear programming, like the Last-In-First-Out or the Most-Often-Selected-Variable are rules not only theoretically finite, but also provide significant flexibility in choosing a pivot element. Based on an implementation of the primal simplex and the monotonic build-up (MBU) simplex method, the practical benefit of the flexibility of these anti-cycling pivot rules is evaluated using public benchmark LP test sets. Our results also provide numerical evidence that the MBU-simplex algorithm is a viable alternative to the traditional simplex algorithm.     

A GENERAL DETERMINISTIC PIVOT METHOD FOR ORIENTED MATROID PROGRAMMING

A new pivot method for oriented matroid progiamming is given out. This mathod is deterministic by nature and is general in the sense that its flexible pivot selection rule allows a family of possible algorithms to be its special cases, including the so called criss-cross algorithm and the Edmonds-Fukuda algorithm as well. As an example of a special implementation of our general method, an extended version of the Edmonds-Fukuda algorithm is presented.     

Oriented matroids

In this paper, the basic properties of oriented matroids are examined. A topological representation theorem for oriented matroids is proven, utilizing the notion of an “arrangement of pseudo-hemispheres”. The duality theorem of linear programming is extended to oriented matroids.     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

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.     

PRIMAL PERTURBATION SIMPLEX ALGORITHMS FOR LINEAR PROGRAMMING

1. IntroductionExtensive research in linear programming, such as [1,2,9,10,if, 12,13,14,19], hasbeen to improve pivot rules to reduce the number of iterations required. Relatively lesseffort was made on perturbing problem data with pivot rules unaltered (for instance, theself--dual parametric method [7] and perturbation--based methods [3,5]). And, becauseof the papametrization, the latter do not proceed as simply as the conventional simplexalgorithm itself.Recently, Pan [17] proposes new pert…     

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.     

A finite crisscross method for oriented matroids

Our paper presents a new finite crisscross method for oriented matroids. Starting from a neither primal nor dual feasible tableau, we reach primal and dual optimal oriented circuits in a finite number of steps if they exist. If there is no optimal tableau then we show that there is no primal feasible circuit or there is no dual feasible cocircuit. So we give a new constructive proof for the general duality theorem (Bland J. Combin. Theory Ser. B 23 (1977), 33–57; Folkman and Lawrence J. Combin. Theory Ser. B 25 (1978), 199–236). Our pivot rule is a generalization of the “anticycling rule” suggested in Bland (op cit; Math. Oper. Res. 2 (1977), 103–107). Finite pivoting rules are given by Edmonds, Fukuda and Todd (Ph.D. dissertation, Univ. of Waterloo, 1982), SIAM Algebraic Discrete Math. 5, No. 4 (1984), 467–485). A general relaxed recursive algorithm was discovered independently by Jensen (Ph.D. thesis, School of OR and IE, Cornell, 1985) which is principally crisscross type. Jensen's is very general and flexible; in fact it can be considered as a family of algorithms. Among the conceivable algorithms in his general family our independently constructed crisscross method is characterized by its extreme simplicity.