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

作     者：Sherali, HD Krishnamurthy, RS Al-Khayyal, FA 

作者机构：Virginia Polytech Inst & State Univ Dept Ind & Syst Engn Blacksburg VA 24061 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA SABRE Technol Solut Ft Worth TX USA 

出 版 物：《JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS》 (优选法理论与应用杂志)

年 卷 期：1998年第99卷第2期

页      面：481-507页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：National Science Foundation, NSF, (DMI 9521398) National Science Foundation, NSF Air Force Office of Scientific Research, AFOSR, (F49620-96-1-0274) Air Force Office of Scientific Research, AFOSR 

主　　题：linear complementarity problem bilinear programming implicit enumeration Lagrangian relaxation 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 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.