A barrier method for dynamic Leontief-type linear programs

In this paper, the authors specialize Gill et al.’s projected Newton barrier method to solve a large-scale linear program of dynamic (i.e. multistage) Leontief-type constraints. They propose an efficient and stable method for solving the least-squares subproblems, the crucial part of the barrier method. The key step is to exploit a special structure of the constraint matrix and reduce the matrix of the normal equation for the least-squares problem to a banded matrix. By comparing the average-case operations count of this specialized barrier method with that of the sparse simplex method, the authors show that this method perfroms at least O(T) faster than the simplex method for such types of linear programs, where T is the number of time periods (i.e. stages).