On the solution of NP-hard linear complementarity problems

A. Faustino, J. Júdice and I. Ribeiro

Abstract

In this paper two enumerative algorithms for the Linear Complementarity Problems (LCP) are discussed. These procedures exploit the equivalence of the LCP into a nonconvex quadratic and a bilinear programs. It is shown that these algorithms are efficient for processing NP-hard LCPs associated with reformulations of the Knapsack problem and should be recommended to solve difficult LCPs.