An optimal-basis identification technique for interior-point linear programming algorithms (Q1174842)

This paper is concerned with a method for identifying an optimal basis for linear programming problems in the setting of interior-point methods. Theoretically an interior-point algorithm with integer data can be terminated when the iterate is sufficiently close to an optimal solution and then is rounded to the nearby optimal solution. A reliable technique for identifying optimal basic and nonbasic variables in the early stage of an interior-point iterative process is developed, so that either an early termination or a reduction in problem size can be obtained and the efficiency of interior-point methods can be improved. To each iterate \(x^ k\) generated by an interior-point algorithm, an indicator vector \(q^ k\) is associated. The vector \(q^ k\) has the property that if \(x^ k\) converges to a nondegenerate vertex \(x^*\), then \(q^ k\) converges to the \(0-1\) vector \(\hbox{sign}(x^*)\). The convergence of \(q^ k\) is quadratically faster than that of \(x^ k\) in the sense that \(\| q^ k-q^*\|=O(\| x^ k-x^*\|^ 2)\). This clear-cut separation and rapid convergence allows one to infer at an intermediate stage of the iterative process which variables will be zero at optimality and which will not. Under suitable assumptions, this method can be extended to handle certain types of degeneracy.