On finding a vertex solution using interior point methods

An approach is proposed to generate a vertex solution while using a primal-dual interior point method to solve linear programs. A controlled random perturbation is made to the cost vector. A method to identify the active constraints at the vertex to which the solutions are converging is given. This basic method is further refined to save computational effort. The proposed approach is tested by using a variation of the primal-dual interior point method. Our method is developed by taking a predictor-corrector approach. In practice this method takes considerably fewer iterations to solve linear programs than methods described by Choi, Monma, and Shanno; Lustig, Marsten, and Shanno; and Domich, Boggs, Donaldson, and Witzgall. Computational results on problems from the NETLIB test set are reported to test our approach for finding vertex solutions. These results show that one perturbation is enough to force the solutions to converge to a vertex. The results indicate that the proposed approach is insensitive to the number of degenerate variables. The results also indicate that the effort required to generate a vertex solution is comparable to that required to solve the problem using an interior point method.