Enumeration approach for linear complementarity problems based on a reformulation-linearization technique

Enumeration approach for linear complementarity problems based on a reformulation-linearization technique

0.00 Avg rating0 Votes
Article ID: iaor19992010
Country: United States
Volume: 99
Issue: 2
Start Page Number: 481
End Page Number: 507
Publication Date: Nov 1998
Journal: Journal of Optimization Theory and Applications
Authors: , ,
Keywords: programming: integer
Abstract:

In this paper, we consider the linear complementarity problem (LCP) and present a global optimisation algorithm based on an application of the reformulation-linearization technique (RLT). The matrix M associated with the LCP is not assumed to possess any special structure. In this approach, the LCP is formulated first as a mixed-integer 0–1 bilinear programming problem. The RLT scheme is then used to derive a new equivalent mixed-integer linear programming formulation of the LCP. An implicit 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. Computational experience on various test problems is presented.

Reviews

Required fields are marked *. Your email address will not be published.