Abstract

On the use of a tabu pivoting technique for solving the linear complementarity problem

This paper describes a pivoting heuristic based on tabu search and its integration into an enumerative framework for solving the Linear Complementarity Problem (LCP). The tabu pivoting heuristic works with basic solutions and performs pivot operations guided by two indicators, one concerning with the satisfaction of the complementarity conditions and the other with the feasibility fo the solution. It incorporates the concept of tabu search employing a strategy that avoids the repetition of recent moves. The heuristic ends when a solution of the LCP is found or after a specified number of iterations. In the latter case, an enumerative algorithm is applied which integrates the tabu pivoting heuristic within a branching framework. Computational experience on test problems is reported to highlight the efficiency of the proposed methodology for solving the LCP.