Comparative analysis of the affine scaling and Karmarkar’s polynomial – time for linear programming

Abstract

The simplex method is the well-known, non-polynomial solution technique for linear programming problems. However, some computational testing has shown that the Karmarkar’s polynomial projective interior point method may perform better than the simplex method on many classes of problems, especially, on problems with large sizes. The affine scaling algorithm is a variant of the Karmarkar’s algorithms. In this paper, we compare the affine scaling and the Karmarkar algorithms using the same test LP problem.

Keywords: Polynomial-time, Complexity bound, Primal LP, Dual LP, Basic Solution, Degenerate Solution, Affine Space, Simplex and Polytope