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

In this paper, we consider the linear complementarity problem (LCP) and present a global optimization 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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of optimization theory and applications 1998-11, Vol.99 (2), p.481-507
Main Authors: SHERALI, H. D, KRISHNAMURTHY, R. S, AL-KHAYYAL, F. A
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Flows in networks. Combinatorial problems
Linear programming
Operational research and scientific management
Operational research. Management science
Optimization. Search problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we consider the linear complementarity problem (LCP) and present a global optimization 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.
ISSN:0022-3239
1573-2878
DOI:10.1023/A:1021734613201