Groupe d’études et de recherche en analyse des décisions

G-2011-44

A Primal-Dual Interior-Point Algorithm for Linear Programming with Selective Addition of Inequalities

et

We present a new primal-dual interior-point algorithm for linear programming problems with equality and inequality constraints. The inequality constraints are initially removed from the problem and selectively added only if they become active during the solution process. After adding an inequality, the algorithm continues with a series of corrector steps to restore centrality and feasibility. We show that the algorithm converges to an optimal solution at which all inequalities are satisfied regardless of whether they are added to the problem or not. We also establish conditions under which the complexity of the algorithm is polynomial in the problem dimension.

, 26 pages