The semismooth algorithm for large scale complementarity problems

Complementarity solvers are continually being challenged by modelers demand ing improved reliability and scalability. Building upon a strong theoretica l background, the semismooth algorithm has the potential to meet both of th ese requirements. We discuss relevant theory associated with the algorithm and then describe a sophisticated implementation in detail. Particular emph asis is given to the use of preconditioned iterative methods to solve the ( nonsymmetric) systems of linear equations generated at each iteration and r obust methods for dealing with singularity. Results on the MCPLIB test suit e indicate that the code is reliable and efficient and scales well to very large problems.