%A Todd S. Munson
%T Algorithms and Environments for Complementarity
%D August 2000
%R 00-02
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X
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.