On the solution of NP-hard linear complementarity problems

Abstract

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