The simplest examples where the simplex method cycles and conditions where expand fails to prevent cycling

This paper introduces a class of linear programming examples that cause the simplex method to cycle and that are the simplest possible examples showing this behaviour. The structure of examples from this class repeats after two iterations. Cycling is shown to occur for both the most negative reduced cost and steepest-edge column selection criteria. In addition it is shown that the expand anti-cycling procedure of Gill et al. is not guaranteed to prevent cycling.Work supported by EPSRC grant GR/J0842This paper is dedicated to Roger Fletcher, a friend and inspiration to us both. The discovery of Rogers book, Practical Methods of Optimization, whilst working in industry, set the first author on the road to Dundee and a career in optimization. Happy 65th birthday, Roger.     

A practical anti-cycling procedure for linearly constrained optimization

A procedure is described for preventing cycling in active-set methods for linearly constrained optimization, including the simplex method. The key ideas are a limited acceptance of infeasibilities in all variables, and maintenance of a working feasibility tolerance that increases over a long sequence of iterations. The additional work per iteration is nominal, and stalling cannot occur with exact arithmetic. The method appears to be reliable, based on computational results for the first 53 linear programming problems in theNetlib set.The material contained in this report is based upon research supported by the Air Force Office of Scientific Research Grant 87-01962; the U.S. Department of Energy Grant DE-FG03-87ER25030; National Science Foundation Grants CCR-8413211 and ECS-8715153; and the Office of Naval Research Contract N00014-87-K-0142.     

On the solution of highly degenerate linear programmes

The solution of scheduling problems often gives rise to highly degenerate linear programmes which cause significant computational difficulties for the revised simplex method. Wolfe's highly effective ad hoc method for overcoming the cycling or stalling problems associated with degeneracy is described. Here it is given a geometric interpretation in terms of finding a direction of recession for a reduced problem which is fundamental to a full understanding of the procedure. An example of an aircrew scheduling problem is used to illustrate the effectiveness of the method.     

有界变量亏基单纯形算法

为克服单纯形算法中退化现象带来的困扰,本文在文[1]的基础上进一步提出亏基有界变量单纯形算法,并证明了算法的收敛性.     

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.     

The simplex method and unrestricted variables

Suppose that the simplex method is applied to a linear programming problem havingm equality constraints andr unrestricted variables. We give a method of performing the steps of the simplex method which reduces the arithmetic operation count byrm at each iteration. This savings in operations is achieved, since the method does not update the rows of the basis inverse associated with the unrestricted variables. Similar computational savings are achieved when the method is applied to the updating of anLU-factorization of the basis matrix.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189 and by a postgraduate fellowship.     

A specialized network simplex algorithm for the constrained maximum flow problem

The constrained maximum flow problem is to send the maximum flow from a source to a sink in a directed capacitated network where each arc has a cost and the total cost of the flow cannot exceed a budget. This problem is similar to some variants of classical problems such as the constrained shortest path problem, constrained transportation problem, or constrained assignment problem, all of which have important applications in practice. The constrained maximum flow problem itself has important applications, such as in logistics, telecommunications and computer networks. In this research, we present an efficient specialized network simplex algorithm that significantly outperforms the two widely used LP solvers: CPLEX and lp_solve. We report CPU times of an average of 27 times faster than CPLEX (with its dual simplex algorithm), the closest competitor of our algorithm.     

A practical anti-degeneracy row selection technique in network linear programming

A characteristic feature of the primal network simplex algorithm (NSA) is that it usually makes a large number of degenerate iterations. Though cycling and even stalling can be avoided by recently introduced pivot rules for NSA, the practical efficiency of these rules is not known yet. For the case when the simplex algorithm is used to solve the continuous linear programming (LP) problem there exists a practical anti-cycling procedure that proved to be efficient. It is based on an expanding relaxation of the individual bound on the variables. In this paper we discuss the adaptation of this method to NSA, taking advantage of the special integer nature of network problems. We also give an account of our experience with these ideas as they are experimentally implemented in the MINET network LP solver. Reductions of CPU time have been achieved on a smaller set of specially structured real-life problems.This research was supported in part by Hungarian Research Fund OTKA 2587, and by DAAD 314 108 060 0 while the author was at Universität Heidelberg, Germany, October, 1990.     

Sensitivity method for basis inverse representation in multistage stochastic linear programming problems

A version of the simplex method for solving stochastic linear control problems is presented. The method uses a compact basis inverse representation that extensively exploits the original problem data and takes advantage of the supersparse structure of the problem. Computational experience indicates that the method is capable of solving large problems.This research was supported by Programs CPBP02.15 and RPI.02.     

New labeling procedures for the basis graph in generalized networks

Labeling procedures for the basis graph of a generalized network are introduced which build on procedures designed for pure networks. Computational results are presented which show that a primal simplex code which uses these procedures is about 60 times faster than a general purpose linear programming code.     

Optimal simplex tableau characterization of unique and bounded solutions of linear programs

Uniqueness and boundedness of solutions of linear programs are characterized in terms of an optimal simplex tableau. LetM denote the submatrix in an optimal simplex tableau with columns corresponding to degenerate optimal dual basic variables. A primal optimal solution is unique iff there exists a nonvacuous nonnegative linear combination of the rows ofM, corresponding to degenerate optimal primal basic variables, which is positive. The set of primal optimal solutions is bounded iff there exists a nonnegative linear combination of the rows ofM which is positive. WhenM is empty, the primal optimal solution is unique.This research was sponsored by the United States Army under Contract No. DAAG29-75-C-0024. This material is based upon work supported by the National Science Foundation under Grant No. MCS-79-01066.     

The simplex method as a global optimizer: A c-programming perspective

In this paper we give a brief account of the important role that the conventional simplex method of linear programming can play in global optimization, focusing on its collaboration with composite concave programming techniques. In particular, we demonstrate how rich and powerful the c-programming format is in cases where its parametric problem is a standard linear programming problem.     

An exterior point simplex algorithm for (general) linear programming problems

We present an exterior point simplex type algorithm that possesses a new monotonic property. A dual feasible basic solution is required to start with. Intermediate solutions are neither primal nor dual feasible. Cycling-free pivoting rules and an exponentional example are presented.     

求解0-1线性整数规划问题的有界单纯形法

提出了一种求解0-1线性整数规划问题的有界单纯形法, 不仅通过数学论证, 讨论了该方法的合理性, 奠定了其数学理论基础, 而且通过求解无容量设施选址问题, 验证了该方法的可行性. 在此基础上, 就该有界单纯形法的不足和存在的问题, 给出了进一步改进的途径和手段.     

Progress in the dual simplex method for large scale LP problems: practical dual phase 1 algorithms

The dual simplex algorithm has become a strong contender in solving large scale LP problems. One key problem of any dual simplex algorithm is to obtain a dual feasible basis as a starting point. We give an overview of methods which have been proposed in the literature and present new stable and efficient ways to combine them within a state-of-the-art optimization system for solving real world linear and mixed integer programs. Furthermore, we address implementation aspects and the connection between dual feasibility and LP-preprocessing. Computational results are given for a large set of large scale LP problems, which show our dual simplex implementation to be superior to the best existing research and open-source codes and competitive to the leading commercial code on many of our most difficult problem instances.     

Bounds on the number of vertices of perturbed polyhedra

Finding the incident edges to a degenerate vertex of a polyhedron is a non-trivial problem. So pivoting methods generally involve a perturbation argument to overcome the degeneracy problem. But the perturbation entails a bursting of each degenerate vertex into a cluster of nondegenerate vertices. The aim of this paper is to give some bounds on the number of these perturbed vertices.     

A pathological case in the reduction of linear programs

This note discusses a pathological case which may arise when a reduction procedure is used to detect implied ‘free’ variables in linear programs. This is the possibility of a spurious unbounded condition. We detail the cause of this anomaly and discuss algorithmic remedies, giving computational experience.     

A theoretical comparison between the simplex method and the basic line search algorithm

A theoretical comparison between the simplex method (SM) and the basic line search method (BLSA) is presented. The explicit formulae for the upper and lower bounds in the BLSA are provided using SM. Further, it is shown that both methods are operationally equivalent.     

Solving a full fuzzy linear programming using lexicography method and fuzzy approximate solution

This paper discusses full fuzzy linear programming (FFLP) problems of which all parameters and variable are triangular fuzzy numbers. We use the concept of the symmetric triangular fuzzy number and introduce an approach to defuzzify a general fuzzy quantity. For such a problem, first, the fuzzy triangular number is approximated to its nearest symmetric triangular number, with the assumption that all decision variables are symmetric triangular. An optimal solution to the above-mentioned problem is a symmetric fuzzy solution. Every FLP models turned into two crisp complex linear problems; first a problem is designed in which the center objective value will be calculated and since the center of a fuzzy number is preferred to (its) margin. With a special ranking on fuzzy numbers, the FFLP transform to multi objective linear programming (MOLP) where all variables and parameters are crisp.     

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.