Enumeration Approach for Linear Complementarity Problems Based on a Reformulation-Linearization Technique

H. D. Sherali, R. S. Krishnamurthy and F. A. Al-Khayyal
Additional contact information
H. D. Sherali: Virginia Polytechnic Institute and State University
R. S. Krishnamurthy: SABRE Technology Solutions
F. A. Al-Khayyal: Georgia Institute of Technology

Journal of Optimization Theory and Applications, 1998, vol. 99, issue 2, No 10, 507 pages

Abstract: Abstract 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.

Keywords: Linear complementarity problem; bilinear programming; implicit enumeration; Lagrangian relaxation; reformulation-linearization technique (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1023/A:1021734613201 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:99:y:1998:i:2:d:10.1023_a:1021734613201

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1021734613201

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().