期刊论文详细信息
PeerJ Computer Science
A new non-monotonic infeasible simplex-type algorithm for Linear Programming
Charalampos P. Triantafyllidis1  Nikolaos Samaras2 
[1] 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;
关键词: Linear programming;    Simplex-type;    Interior point method;    Exterior point;    Non-monotonic;    Infeasible;   
DOI  :  10.7717/peerj-cs.265
来源: DOAJ
【 摘 要 】

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.

【 授权许可】

Unknown   

  文献评价指标  
  下载次数:0次 浏览次数:0次