Technical Note—A Note on Reinverting the Dantzig-Wolfe Type Decomposed LP Basis

This note reports an efficient routine that has been developed and successfully applied to the reinversion of decomposed LP bases of the Dantzig-Wolfe type. In sum, if r is the total number of subproblems in the original LP problem and k is the number of subproblem vectors in the decomposed basis, then only k − r Gauss-Jordan iterations are needed to invert the decomposed basis. The larger r, the more efficient and accurate the routine. This reduction in the number of Gauss-Jordan iterations is accomplished by finding the inverse of the wrong basis rapidly, and then making the necessary corrections to get the inverse of the right basis.