TY - JOUR

T1 - On finding a vertex solution using interior point methods

AU - Mehrotra, Sanjay

N1 - Funding Information:
*This research was supported in part by the National Science Foundation 8810107 and Office of Naval Research grant N00014-87-K-0214. tE-mail: mehrotra@iems.nuu.edu.

PY - 1991/7/1

Y1 - 1991/7/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0003337558&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0003337558&partnerID=8YFLogxK

U2 - 10.1016/0024-3795(91)90277-4

DO - 10.1016/0024-3795(91)90277-4

M3 - Article

AN - SCOPUS:0003337558

VL - 152

SP - 233

EP - 253

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - C

ER -