Parallel distributed-memory simplex for large-scale stochastic LP problems

We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g., in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates.     

Markov decision processes for infinite horizon problems solved with the cosine simplex method

This article presents a new method of linear programming (LP) for solving Markov decision processes (MDPs) based on the simplex method (SM). SM has shown to be the most efficient method in many practical problems; unfortunately, classical SM has an exponential complexity. Therefore, new SMs have emerged for obtaining optimal solutions in the most efficient way. The cosine simplex method (CSM) is one of them. CSM is based on the Karush Kuhn Tucker conditions, and is able to efficiently solve general LP problems. This work presents a new method named the Markov Cosine Simplex Method (MCSM) for solving MDP problems, which is an extension of CSM. In this article, the efficiency of MCSM is compared to the traditional revised simplex method (RSM); experimental results show that MCSM is far more efficient than RSM.     

A numerically exact implementation of the simplex method

The numerical performance of the state-of-the-art simplex based optimizers is good. At the same time, a newly arising LP problem can cause troubles still. This is exactly what happened in the Summer of 1992. The appearance of a hard LP problem motivated the development of the idea of a numerically exact implementation of the simplex method. It is based on a super register (SR) capable of accumulating inner products with arbitrary accuracy. The necessary operations of SR that require assembly level programming are introduced. Vectors of super registers would require prohibitively much memory. Therefore, a single-SR technique is proposed that entails the reorganization of parts of the simplex method. The ideas have been implemented in the MILP LP optimizer. Experiences show that solution speed decreases by 30–50 percent but robustness increases which may be important in case of critical problems. A framework is outlined for a system where the advantages of the traditional and the SR technique can co-operate efficiently.This research was partly supported by Hungarian Research Fund OTKA 2587.     

On the use of the simplex algorithm for the absolute deviation curve fitting problem

Linear curve-fitting problems are commonly solved using a criterion which minimises the sum of the squares of deviations of observations from the line. The legitimacy of this operation relies on a number of assumptions which in practice are often left untested. Alternatively the curve-fitting exercise is justified by its computational tractibility. An alternative procedure which fits lines using a criterion of minimising the sum of the absolute deviations of observations from the line is acknowledged to have attractive properties, but is often avoided because of computational difficulties in solution. In fact this problem has long been known to be amenable to solution by linear programming, and in this paper we present some results, commentary and advice based on the use of three LP codes to solve the problem. Two of these codes are conventional implementations of the simplex method while the third is a special purpose code written for just this problem. Live data from a problem of batch manufacture was used, and the influence of data is part of the investigation. At least some of the advice is contrary to that offered by earlier authors.     

Towards a practical parallelisation of the simplex method

The simplex method is frequently the most efficient method of solving linear programming (LP) problems. This paper reviews previous attempts to parallelise the simplex method in relation to efficient serial simplex techniques and the nature of practical LP problems. For the major challenge of solving general large sparse LP problems, there has been no parallelisation of the simplex method that offers significantly improved performance over a good serial implementation. However, there has been some success in developing parallel solvers for LPs that are dense or have particular structural properties. As an outcome of the review, this paper identifies scope for future work towards the goal of developing parallel implementations of the simplex method that are of practical value.     

Application of Nelder-Mead simplex method for unconfined seepage problems

In unconfined seepage problems, the phreatic line resulted from mesh deforming methods is rarely a smooth and continuous curve. The main problem is at the meeting point of the phreatic line with the down stream face of the dam where the phreatic line must be tangent to the seepage face according to the fluid continuity principle. In this paper a mesh deforming finite element method based on Nelder-Mead simplex optimization is presented to solve this problem. The phreatic line is approximated by a 4th degree polynomial and Nelder-Mead simplex method is used to calculate the polynomial’s coefficients minimizing an error function which is introduced based on the conditions on the phreatic line. Tangentiality of the phreatic line to the seepage face is introduced in the solution by a constraint in optimization procedure. The results of the presented method are verified by the results of the nonlinear finite element and other mesh deforming methods.     

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.     

A novel method for solving linear programming problems with symmetric trapezoidal fuzzy numbers

Linear programming (LP) is a widely used optimization method for solving real-life problems because of its efficiency. Although precise data are fundamentally indispensable in conventional LP problems, the observed values of the data in real-life problems are often imprecise. Fuzzy sets theory has been extensively used to represent imprecise data in LP by formalizing the inaccuracies inherent in human decision-making. The fuzzy LP (FLP) models in the literature generally either incorporate the imprecisions related to the coefficients of the objective function, the values of the right-hand-side, and/or the elements of the coefficient matrix. We propose a new method for solving FLP problems in which the coefficients of the objective function and the values of the right-hand-side are represented by symmetric trapezoidal fuzzy numbers while the elements of the coefficient matrix are represented by real numbers. We convert the FLP problem into an equivalent crisp LP problem and solve the crisp problem with the standard primal simplex method. We show that the method proposed in this study is simpler and computationally more efficient than two competing FLP methods commonly used in the literature.     

On CP, LP and other piecewise perturbation methods for the numerical solution of the Schr?dinger equation

The piecewise perturbation methods (PPM) have proven to be very efficient for the numerical solution of the linear time-independent Schr?dinger equation. The underlying idea is to replace the potential function piecewisely by simpler approximations and then to solve the approximating problem. The accuracy is improved by adding some perturbation corrections. Two types of approximating potentials were considered in the literature, that is piecewise constant and piecewise linear functions, giving rise to the so-called CP methods (CPM) and LP methods (LPM). Piecewise polynomials of higher degree have not been used since the approximating problem is not easy to integrate analytically. As suggested by Ixaru (Comput Phys Commun 177:897–907, 2007), this problem can be circumvented using another perturbative approach to construct an expression for the solution of the approximating problem. In this paper, we show that there is, however, no need to consider PPM based on higher-order polynomials, since these methods are equivalent to the CPM. Also, LPM is equivalent to CPM, although it was sometimes suggested in the literature that an LP method is more suited for problems with strongly varying potentials. We advocate that CP schemes can (and should) be used in all cases, since it forms the most straightforward way of devising PPM and there is no advantage in considering other piecewise polynomial perturbation methods.     

On CP,LP and other piecewise perturbation methods for the numerical solution of the Schrödinger equation

The piecewise perturbation methods (PPM) have proven to be very efficient for the numerical solution of the linear time-independent Schrödinger equation. The underlying idea is to replace the potential function piecewisely by simpler approximations and then to solve the approximating problem. The accuracy is improved by adding some perturbation corrections. Two types of approximating potentials were considered in the literature, that is piecewise constant and piecewise linear functions, giving rise to the so-called CP methods (CPM) and LP methods (LPM). Piecewise polynomials of higher degree have not been used since the approximating problem is not easy to integrate analytically. As suggested by Ixaru (Comput Phys Commun 177:897–907, 2007), this problem can be circumvented using another perturbative approach to construct an expression for the solution of the approximating problem. In this paper, we show that there is, however, no need to consider PPM based on higher-order polynomials, since these methods are equivalent to the CPM. Also, LPM is equivalent to CPM, although it was sometimes suggested in the literature that an LP method is more suited for problems with strongly varying potentials. We advocate that CP schemes can (and should) be used in all cases, since it forms the most straightforward way of devising PPM and there is no advantage in considering other piecewise polynomial perturbation methods.     

Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems

Convex quadratically constrained quadratic problems are considered. It is shown that such problems can be transformed to aconic form. The feasible set of the conic form is the intersection of a direct product of standard quadratic cones intersected with a hyperplane (the analogue of a simplex), and a linear subspace. For a problem of such form, the analogue of Karmarkar's projective transformation and logarithmic barrier function are built. This allows us to extend “word by word” the method of Karmarkar for LP to QCQP and allows us to obtain a similar polynomial worst-case bound for the number of iterations.     

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.     

Approximate and exact algorithms for the fixed-charge knapsack problem

The subject of this paper is the formulation and solution of a variation of the classical binary knapsack problem. The variation that is addressed is termed the “fixed-charge knapsack problem”, in which sub-sets of variables (activities) are associated with fixed costs. These costs may represent certain set-ups and/or preparations required for the associated sub-set of activities to be scheduled. Several potential real-world applications as well as problem extensions/generalizations are discussed. The efficient solution of the problem is facilitated by a standard branch-and-bound algorithm based on (1) a non-iterative, polynomial algorithm to solve the LP relaxation, (2) various heuristic procedures to obtain good candidate solutions by adjusting the LP solution, and (3) powerful rules to peg the variables. Computational experience shows that the suggested branch-and-bound algorithm shows excellent potential in the solution of a wide variety of large fixed-charge knapsack problems.     

An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems

In this paper a local integral simplex algorithm will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex algorithm creates and solves the problems in a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc. The solution to at least one of these subproblems is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is an optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n.A method for programming the algorithms in this paper to run on parallel computers is discussed briefly.     

基于线性规划核心矩阵的单纯形算法

本文讨论了线性规划中的核心矩阵及其特性,探讨了利用核心矩阵实现单纯形算法的可能性,并进一步提出了一个基于核心矩阵的两阶段原始一对偶单纯形方法,该方法通过原始和对偶两个阶段的迭代,可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界．在试验的22个问题中,该算法的计算效率总体优于基于传统单纯形方法的MINOS软件．     

An Algorithm for Approximate Multiparametric Linear Programming

Multiparametric programming considers optimization problems where the data are functions of a parameter vector and describes the optimal value and an optimizer as explicit functions of the parameters. In this paper, we consider a linear program where the right-hand side is an affine function of a parameter vector; we propose an algorithm for approximating its solution. Given a full-dimensional simplex in the parameter space and an optimizer for each simplex vertex, the algorithm formulates the linear interpolation of the given solutions as an explicit function of the parameters, giving a primal feasible approximation of an optimizer inside the simplex. If the resulting absolute error in the objective exceeds a prescribed tolerance, then the algorithm subdivides the simplex into smaller simplices where it applies recursively. We propose both a basic version and a refined version of the algorithm. The basic version is polynomial in the output size, provided a polynomial LP solver is used; the refined version may give a smaller output. A global error bound for the optimizer is derived and some computational tests are discussed.     

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.     

A Convergent Variant of the Nelder–Mead Algorithm

The Nelder–Mead algorithm (1965) for unconstrained optimization has been used extensively to solve parameter estimation and other problems. Despite its age, it is still the method of choice for many practitioners in the fields of statistics, engineering, and the physical and medical sciences because it is easy to code and very easy to use. It belongs to a class of methods which do not require derivatives and which are often claimed to be robust for problems with discontinuities or where the function values are noisy. Recently (1998), it has been shown that the method can fail to converge or converge to nonsolutions on certain classes of problems. Only very limited convergence results exist for a restricted class of problems in one or two dimensions. In this paper, a provably convergent variant of the Nelder–Mead simplex method is presented and analyzed. Numerical results are included to show that the modified algorithm is effective in practice.     

A bound for the number of different basic solutions generated by the simplex method

In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems (LP) having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the positive elements of primal basic feasible solutions. When the problem is primal nondegenerate, it becomes a bound for the number of iterations. The result includes strong polynomiality for Markov Decision Problem by Ye (http://www.stanford.edu/~yyye/simplexmdp1.pdf, 2010) and utilize its analysis. We also apply our result to an LP whose constraint matrix is totally unimodular and a constant vector b of constraints is integral.