
Complementarity problems arise in a wide variety of disciplines.  Prototypical
examples include the Wardropian and Walrasian equilibrium models encountered 
in the engineering and economic disciplines and the first order optimality 
conditions for nonlinear programs from the optimization community.  The main
focus of this thesis is algorithms and environments for solving 
complementarity problems.

Environments, such as AMPL and GAMS, are used by practitioners to easily 
write large, complex models.  Support for these 
packages is provided by PATH 4.x and SEMI through the customizable solver 
interface specified in this thesis.  The main design feature is the 
abstraction of core components from the code with implementations tailored 
to a particular environment supplied either at compile or run time.
This solver interface is then used to develop new links to the MATLAB and 
NEOS tools.

Preprocessing techniques are an integral part of linear and mixed
integer programming codes and are primarily used to reduce the size and 
complexity of a model prior to solving it.  For example, wasted computation 
is avoided
when an infeasible model is detected.  This thesis documents the new 
techniques for preprocessing complementarity problems contained in the 
PATH 4.x and SEMI algorithms.

PATH 4.x is more reliable than prior versions of the code and has been able 
to find solutions to previously unsolvable models.  The reasons for the 
improvement are discussed in this thesis and include new theoretical 
developments for a globalization scheme based on the Fischer-Burmeister 
merit function, and enhancements made to the linear complementarity solver, 
nonmonotone linesearch, and restart strategy.

SEMI is an alternative to PATH 4.x based on the semismooth algorithm.  The 
main computation in PATH 4.x is to solve linear complementarity problems,
which can be quite expensive.  The new SEMI code described in this thesis only 
solves linear systems of equations and uses iterative methods to process
very large models.

The theme of this thesis is ``enabling'' technologies in 
complementarity: environments enable practitioners to easily specify 
models; sophisticated codes enable them to solve the models; and theory 
assures them that the algorithm is well-defined and efficiently processes 
models.
