An extension of Karmarkar's algorithm for linear programming using dual variables (Q1090601)

The recent, but already classic projective algorithm of Karmarkar for linear programs is an interior point method, i.e. it generates a sequence of relative interior points of the feasible region, thereby reducing the objective value by a fixed factor. With an all integer problem the process may thus be stopped after a polynomial number of steps and the optimal solution obtained by rounding. The algorithm does however not generate dual solutions, of great importance in practice. This paper describes a variant of Karmarkar's method in which both primal and dual solutions are generated, converging to optimal primal and dual solutions respectively. The method applies when the optimal value of the problem is unknown, and has the same convergence properties as Karmarkar's. Details on efficient implementation using OR factorizations indicate the complexities of the calculations involved at each step, and shows how extreme point solutions may be derived at each step with minor additional work.