On finding a vertex solution using interior point methods (Q1174841)

An approach is proposed to generate a vertex solution while using a primal-dual interior-point method to solve linear programs \(\min\{z=c^ Tx\mid Ax=b, x\geq 0\}\). Let \(z^*\) denote the optimal objective value of the linear program, and \(v^*\) be a vertex solution of the linear program satisfying \(c^ Tv^*-z^*\leq\varepsilon\). The problem of finding the vertex solution \(v^*\) can be solved within the framework of implementations of interior-point methods. When the choice of \(\varepsilon\) is properly small the vertex solution \(v^*\) is the optimal solution of the linear program. The known practical approaches to finding a vertex from an interior solution perform computations similar to those in the simplex method. However there are potential disadvantages in using such approach to find a vertex solution. In the paper, an approach is proposed. The approach makes a controlled random perturbation to the cost vector to improve the likelihood that the perturbed linear program has unique solution. The size of the perturbation is controlled so that the objective value at the optimal solution of the perturbed problem is within the specified tolerance of \(z^*\). A method to identify the active constraints at the vertex to which the solutions are converging is given. The 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 on problems from the NETLIB test set.