A Two Dimensional Search Primal Affine Scaling Interior Point Algorithm for Linear Programs

摘要

Interior point methods optimally solve linear programs by moving between feasible interior solutions. This class of algorithms typically move between solutions by following a single search direction, which requires the solution to a one dimensional subspace problem at each iteration. This paper presents a two dimensional search primal affine scaling interior point algorithm, which considers two search directions instead of one. These search directions create a two dimensional subspace problem that is defined by the intersection of the affine combination of the two search directions and the feasible region of the linear program. Linear time algorithms exist to solve such a simple problem and the optimal solution is used to compute the next feasible interior solution. Preliminary computational results show that this new technique improves the objective function value at each iteration approximately 30% more than the classical one dimensional search primal affine scaling interior point algorithm.