The Semismooth Algorithm for Large Scale Complementarity Problems

Complementarity solvers are continually being challenged by modelers demanding improved reliability and scalability. Building upon a strong theoretical background, the semismooth algorithm has the potential to meet both of these requirements. We briefly discuss relevant theory associated with the algorithm and describe a sophisticated implementation in detail. Particular emphasis is given to robust methods for dealing with singularities in the linear system and to large scale issues. Results on the MCPLIB test suite indicate that the code is robust and has the potential to solve very large problems. Computer Sciences Department, University of Wisconsin --- Madison, 1210 West Dayton Street, Madison, WI 53706, USA; e-mail: ftmunson,ferrisg@cs.wisc.edu. The research of this author was partially supported by National Science Foundation Grants CCR-9619765 and CDA-9726385 and Air Force Office of Scientific Research Grant F49620-98-1-0417. y Dipartimento di Informatica e Sistemistica, Uni..