ABSTRACT
This chapter presents affine scaling, the first such algorithm to challenge the dominance of the simplex method, and the logarithmic barrier method, which is widely used and is usually faster than simplex on a large sparse LPs. Affine scaling was the method of choice when researchers initially tried to replicate Karmarkar's reported computational results. Later, it was discovered that affine scaling had been invented years before by Dikin. The major limitation of Newton's method is that it needs a starting point that is not far from the point it is seeking. Interior point algorithms for linear programming employ nonlinear programming methods to move in the interior of the feasible region. Karmarkar persisted in his claims. Many people were skeptical. Later, it was discovered that affine scaling had been invented years before by Dikin. Some refer to the algorithm as “Dikin's”.
