Enumeration Approach for Linear Complementarity Problems Based on a Reformulation-Linearization Technique |
| |
| Authors: | Sherali H D Krishnamurthy R S Al-Khayyal F A |
| |
| Institution: | (1) Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, Virginia;(2) SABRE Technology Solutions, Fort Worth, Texas;(3) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia |
| |
| 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 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
