An LP-based successive overrelaxation method for linear complementarity problems (Q1093555)

A sparsity preserving LP-based SOR method for solving classes of linear complementarity problems including the case where the given matrix is positive semidefinite is proposed. The LP subproblems need be solved only approximately by an SOR method. Heuristic enhancement is discussed. Numerical results for a special class of problems are presented, which show that the heuristic enhancement is very effective and the resulting program can solve problems of more than 100 variables in a few seconds even on a personal computer.