A combined phase I-phase II projective algorithm for linear programming (Q1114588): Difference between revisions

For the fractional linear programming problem an algorithm of projective type is devised closely related to Karmarkar's algorithm. The proposed algorithm considers the constraint that an artificial variable be zero at the solution of the original problem explicitly. The inclusion of such a constraint allows to apply the algorithm to standard linear programming problems without any special precautions or conversion to a primal-dual form. The algorithm either detects inconsistency (for example infeasibility) of the problem or generates a sequence of iterations converging to the solution with a corresponding sequence of lower bounds of the optimal value.