A New Exterior Point Algorithm for Linear Programming Problems


Konstantinos Dosios, Konstantinos Paparrizos




We present a simplex type algorithm for the linear programming problem min ${ c^T : A \cdot x = b, x \geq 0 }$. It solves a sequence of problems of increasing dimension. The path generated by the algorithm contains basic solutions that are neither primal nor dual feasible. Results from an elementary computational study are also presented.