Experimental Behavior of Jurik’s Nearest Point Approach Algorithm for Linear Programming

Abstract

T. Jurik recently proposed a new algorithm for solving linear programming problems. The algorithm is iterative, finding points on the boundary of the problem’s convex polyhedron. Global convergence of the algorithm is an open question. Jurik benchmarked the performance of the algorithm on standard sets of linear optimization problems, and the algorithm was on par with commonly used ones, and sometimes beating the simplex method by a wide margin. In this note we concentrate on testing local behavior of the algorithm near a vertex in the three dimensional Euclidean space. Our experiments indicate that the behavior of the algorithm is mostly very fast, but there appear to be cases where its behavior is worse than the simplex method.