ENUMERATION APPROACH FOR LINEAR COMPLEMENTARITY-PROBLEMS BASED ON A REFORMULATION-LINEARIZATION TECHNIQUE

In this paper, we consider the linear complementarity problem (LCP) an d present a global optimization algorithm based on an application of t he reformulation-linearization technique (RLT). The matrix M associate d with the LCP is not assumed to possess any special structure. In thi s approach, the LCP is formulated first as a mixed-integer 0-1 bilinea r programming problem. The RLT scheme is then used to derive a new equ ivalent mixed-integer linear programming formulation of the LCP. An im plicit enumeration scheme is developed that uses Lagrangian relaxation , strongest surrogate and strengthened cutting planes, and a heuristic , designed to exploit the strength of the resulting linearization. Com putational experience on various test problems is presented.