Preprocessing Complementarity Problems

Abstract

Preprocessing techniques are extensively used by linear and integer programming communities as a means to improve model formulation by reducing size and complexity. Adaptations and extension of these methods for use within the complementarity framework are detailed. 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 utilized complementarity theory to eliminate variables. The methodology is successfully employed to preprocess several models.