Hd. Sherali et al., ENUMERATION APPROACH FOR LINEAR COMPLEMENTARITY-PROBLEMS BASED ON A REFORMULATION-LINEARIZATION TECHNIQUE, Journal of optimization theory and applications, 99(2), 1998, pp. 481-507
Citations number
29
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science
In this paper, we consider the linear complementarity problem (LCP) an
d present a global optimization algorithm based on an application of t
he reformulation-linearization technique (RLT). The matrix M associate
d with the LCP is not assumed to possess any special structure. In thi
s approach, the LCP is formulated first as a mixed-integer 0-1 bilinea
r programming problem. The RLT scheme is then used to derive a new equ
ivalent mixed-integer linear programming formulation of the LCP. An im
plicit 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. Com
putational experience on various test problems is presented.