On the implementation of an optimal basis identification procedure for interior point method

In this study, we deal with the implementation of an optimal basis identification procedure for interior point methods. Our implementation is based on Megiddo's strongly polynomial algorithm applied to Andersen and Ye's approximate LP construction. Several techniques are explained such as the use of effective indicator for obtaining optimal partition when constructing the approximate LP, the efficient implementation of the problem reduction technique proposed by Andersen, the crashing procedure needed for fast dual phase of Megiddo's algorithm, and the construction of the stable initial basis. By experimental comparison, we show that our implementation is superior to the crossover scheme implementation.