A new non-monotonic infeasible simplex-type algorithm for Linear Programming

Charalampos P Triantafyllidis; Nikolaos Samaras

doi:10.7717/peerj-cs.265

A new non-monotonic infeasible simplex-type algorithm for Linear Programming

PeerJ Comput Sci. 2020 Mar 30:6:e265. doi: 10.7717/peerj-cs.265. eCollection 2020.

Authors

Charalampos P Triantafyllidis¹, Nikolaos Samaras²

Affiliations

¹ Computational Biology & Integrative Genomics, Department of Oncology, Medical Sciences Division, University of Oxford, Oxford, United Kingdom.
² Department of Applied Informatics, School of Information Sciences, University of Macedonia, Thessaloniki, Greece.

Abstract

This paper presents a new simplex-type algorithm for Linear Programming with the following two main characteristics: (i) the algorithm computes basic solutions which are neither primal or dual feasible, nor monotonically improving and (ii) the sequence of these basic solutions is connected with a sequence of monotonically improving interior points to construct a feasible direction at each iteration. We compare the proposed algorithm with the state-of-the-art commercial CPLEX and Gurobi Primal-Simplex optimizers on a collection of 93 well known benchmarks. The results are promising, showing that the new algorithm competes versus the state-of-the-art solvers in the total number of iterations required to converge.

Keywords: Exterior point; Infeasible; Interior point method; Linear programming; Mathematical programming; Non-monotonic; Optimization; Simplex-type.

Grants and funding

The authors received no funding for this work.