Karmarkar's Algorithm - The Algorithm

The Algorithm

Consider a Linear Programming problem in matrix form:

maximize cTx
subject to	Ax ≤ b.

The algorithm determines the next feasible direction toward optimality and scales back by a factor 0 < γ ≤ 1.

Karmarkar's algorithm is rather complicated. A simplified version, called the affine-scaling method, proposed and analyzed by others, can be described succinctly as follows. Note that the affine-scaling algorithm, while efficient in practice, is not a polynomial time algorithm.

Algorithm Affine-Scaling Input: A, b, c, stopping criterion, . do while stopping criterion not satisfied if then return unbounded end if end do