DEVEX
Pivot selection methods of the devex LP code. Pivot column and row selection methods used by the Devex code since 1965 are published here for the first time. After a fresh look at the iteration process, the author introduces dynamic column weighting factors as a means of estimating gradients for the purpose of selecting a maximum gradient column. The consequent effect of this column selection on rounding error is observed. By allowing that a constraint may not be positioned so exactly as its precise representation in the computer would imply, a wider choice of pivot row is made available, so making room for a further selection criterion based on pivot size. Three examples are given of problems having between 2500 and 5000 rows, illustrating the overall time and iteration advantages over the standard simplex methods used today. The final illustration highlights why these standard methods take so many iterations. These algorithms were originally coded for the Atlas computer and were re-coded in 1969 for the Univac 1108.
Keywords for this software
References in zbMATH (referenced in 93 articles )
Showing results 1 to 20 of 93.
Sorted by year (- Forsgren, Anders; Gill, Philip E.; Wong, Elizabeth: Primal and dual active-set methods for convex quadratic programming (2016)
- Riplinger, Martin; Krause, Michael; Louis, Alfred K.; Xu, Chihao: A new local dimming algorithm based on the simplex method (2016)
- Lubin, Miles; Dunning, Iain: Computing in operations research using Julia (2015)
- Omer, Jérémy; Rosat, Samuel; Raymond, Vincent; Soumis, François: Improved primal simplex: a more general theoretical framework and an extended experimental analysis (2015)
- Ferreau, Hans Joachim; Kirches, Christian; Potschka, Andreas; Bock, Hans Georg; Diehl, Moritz: qpOASES: a parametric active-set algorithm for quadratic programming (2014)
- Towhidi, Mehdi; Desrosiers, Jacques; Soumis, François: The positive edge criterion within COIN-OR’s CLP (2014)
- Fábián, Csaba I.; Papp, Olga; Eretnek, Krisztián: Implementing the simplex method as a cutting-plane method, with a view to regularization (2013)
- Lubin, Miles; Hall, J.A.Julian; Petra, Cosmin G.; Anitescu, Mihai: Parallel distributed-memory simplex for large-scale stochastic LP problems (2013)
- Bixby, Robert E.: A brief history of linear and mixed-integer programming computation (2012)
- Borghi, Alexandre; Darbon, Jér^ome; Peyronnet, Sylvain: Exact optimization for the $\ell ^1$-compressive sensing problem using a modified Dantzig-Wolfe method (2011)
- Elhallaoui, Issmail; Metrane, Abdelmoutalib; Soumis, François; Desaulniers, Guy: Multi-phase dynamic constraint aggregation for set partitioning type problems (2010)
- Hall, J.A.J.: Towards a practical parallelisation of the simplex method (2010)
- Maros, István: Computational study of the GDPO dual phase-1 algorithm (2010)
- Pan, Pingqi: A fast simplex algorithm for linear programming (2010)
- Hu, Jian-Feng; Pan, Ping-Qi: An efficient approach to updating simplex multipliers in the simplex algorithm (2008)
- Koberstein, Achim: Progress in the dual simplex algorithm for solving large scale LP problems: Techniques for a fast and stable implementation (2008)
- Pan, Ping-Qi: A primal deficient-basis simplex algorithm for linear programming (2008)
- Pan, Ping-Qi: Efficient nested pricing in the simplex algorithm (2008)
- Pan, Ping-Qi: A largest-distance pivot rule for the simplex algorithm (2008)
- Ben-Ameur, Walid; Neto, José: Acceleration of cutting-plane and column generation algorithms: applications to network design (2007)