Preprocessing Complementarity Problems

Preprocessing techniques are extensively used in the linear and integer programming communities as a means to improve model formulation by reducing size and complexity. Adaptations and extensions of these methods for use within the complementarity framework are detailed and shown to be effective on practical models. The preprocessor developed is comprised of two phases. The first recasts a complementarity problem as a variational inequality over a polyhedral set and exploits the uncovered structure to fix variables and remove constraints. The second discovers information about the function and utilizes complementarity theory to eliminate variables. The methodology is successfully employed to preprocess several models.