  Column generation is often used to solve multi-commodity flow problems. A
program for column generation always includes a module that solves a linear
equation. In this paper, we address three major issues in solving linear
problem during column generation procedure which are (1) how to employ the
sparse property of the coefficient matrix; (2) how to reduce the size of the
coefficient matrix; and (3) how to reuse the solution to a similar equation. To
this end, we first analyze the sparse property of coefficient matrix of linear
equations and find that the matrices occurring in iteration are very sparse.
Then, we present an algorithm locSolver (for localized system solver) for
linear equations with sparse coefficient matrices and right-hand-sides. This
algorithm can reduce the number of variables. After that, we present the
algorithm incSolver (for incremental system solver) which utilizes similarity
in the iterations of the program for a linear equation system. All three
techniques can be used in column generation of multi-commodity problems.
Preliminary numerical experiments show that the incSolver is significantly
faster than the existing algorithms. For example, random test cases show that
incSolver is at least 37 times and up to 341 times faster than popular solver
LAPACK.
