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

*(English)*Zbl 0911.90328Summary: 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.

##### MSC:

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

90C11 | Mixed integer programming |

##### Keywords:

bilinear programming; implicit enumeration; linear complementarity problem; global optimization algorithm; reformulation linearization technique; Lagrangian relaxation##### Software:

XMP
PDF
BibTeX
XML
Cite

\textit{H. D. Sherali} et al., J. Optim. Theory Appl. 99, No. 2, 481--507 (1998; Zbl 0911.90328)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Murty, K. G., Linear Complementarity, Linear and Nonlinear Programming, Helderman Verlag, Berlin, Germany, 1988. |

[2] | Cottle, R. W., Pang, J. S., and Stone, R. E., The Linear Complementarity Problem, Academic Press, San Diego, California, 1992. · Zbl 0757.90078 |

[3] | Ye, Y., and Pardalos, P. M., A Class of Linear Complementarity Problems Solvable in Polynomial Time, Linear Algebra and Its Applications, Vol. 152, pp. 3–17, 1991. · Zbl 0742.65054 |

[4] | Kojima, M., Megiddo, N., Noma, T., and Yoshise, A., A Unified Approach to Interior-Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science, Springer Verlag, Berlin, Germany, Vol. 538, 1991. · Zbl 0745.90069 |

[5] | Pardalos, P. M., Ye, Y., Han, C. G., and Kalinski, J., Solution of P-Matrix Linear Complementarity Problems Using a Potential Reduction Algorithm, SIAM Journal on Matrix Analysis and Applications, Vol. 14, pp. 1048–1060, 1993. · Zbl 0788.65072 |

[6] | Al-Khayyal, F. A., An Implicit Enumeration Procedure for the Linear Complementarity Problem, Mathematical Programming Study, Vol. 17, pp. 1–21, 1987. · Zbl 0623.90079 |

[7] | Pardalos, P. M., and Rosen, J. B., Global Optimization Approach to the Linear Complementarity Problem, SIAM Journal on Scientific and Statistical Computations, Vol. 9, pp. 341–353, 1988. · Zbl 0646.65051 |

[8] | JÚdice, J. J., and Faustino, A. M., An Experimental Investigation of Enumeration Methods for Linear Complementarity Problems, Computers and Operations Research, Vol. 15, pp. 417–426, 1988. · Zbl 0647.90095 |

[9] | Mangasarian, O., The Linear Complementarity Problem as a Separable Bilinear Program, Journal of Global Optimization, Vol. 6, pp. 153–161, 1995. · Zbl 0835.90102 |

[10] | Sherali, H. D., Krishnamurthy, R., and Al-Khayyal, F. A., Enhanced Intersection Cutting Plane Approach for Linear Complementarity Problems, Journal of Optimization Theory Applications, Vol. 90, pp. 183–201, 1996. · Zbl 0866.90126 |

[11] | Dorn, W. S., Self-Dual Quadratic Programs, SIAM Journal on Applied Mathematics, Vol. 9, pp. 51–54, 1961. · Zbl 0104.14403 |

[12] | Eaves, B. C., The Linear Complementarity Problem, Management Science, Vol. 17, pp. 612–634, 1971. · Zbl 0228.15004 |

[13] | Mangasarian, O., Equivalence of the Complementarity Problem to a System of Nonlinear Equations, SIAM Journal on Applied Mathematics, Vol. 31, pp. 89–92, 1977. · Zbl 0339.90051 |

[14] | Al-Khayyal, F. A., On Solving Linear Complementarity Problems as Bilinear Programs, Arabian Journal for Science and Engineering, Vol. 15, pp. 639–646, 1990. · Zbl 0721.90073 |

[15] | Sherali, H. D., and Adams, W. P., A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems, SIAM Journal on Discrete Mathematics, Vol. 3, pp. 411–430, 1990. · Zbl 0712.90050 |

[16] | Sherali, H. D., and Adams, W. P., A Hierarchy of Relaxations and Convex Hull Characterizations for Mixed-Integer Zero-One Programming Problems, Discrete Applied Mathematics, Vol. 52, pp. 83–106, 1994. · Zbl 0819.90064 |

[17] | Adams, W. P., and Sherali, H. D., Mixed-Integer Bilinear Programming Problems, Mathematical Programming, Vol. 59, pp. 279–305, 1993. · Zbl 0801.90085 |

[18] | Sherali, H. D., and Myers, D. C., The Design of Branch-and-Bound Algorithms for a Class of Nonlinear Integer Programs, Annals of Operations Research, Vol. 5, pp. 463–484, 1986. |

[19] | Sherali, H. D., and Ulular, O., A Primal-Dual Conjugate Subgradient Algorithm for Specially Structured Linear and Convex Programming Problems, Applied Mathematics and Optimization, Vol. 20, pp. 193–221, 1989. · Zbl 0675.90069 |

[20] | Bazaraa, M. S., Sherali, H. D., and Shetty, C. M., Nonlinear Programming: Theory and Algorithms, 2nd Edition, John Wiley and Sons, New York, New York, 1993. |

[21] | Camerini, P. M., Fratta, L., and Maffioli, F., On Improving Relaxation Methods by Modified Gradient Techniques, Mathematical Programming Study, Vol. 3, pp. 26–34, 1975. · Zbl 0357.90031 |

[22] | Sherali, H. D., and Choi, G., Recovery of Primal Solutions When Using Subgradient Optimization Methods to Solve Lagrangian Duals of Linear Programs, Operations Research Letters, Vol. 19, pp. 105–113, 1996. · Zbl 0871.90054 |

[23] | Shor, N. S., Minimization Methods for Nondifferentiable Functions, Springer Verlag, Berlin, Germany, 1985 (Translated from Russian). · Zbl 0561.90058 |

[24] | Rardin, R., and Unger, V., Surrogate Constraints and the Strength of Bounds Derived from 0–1 Benders Partitioning Procedures, Operations Research, Vol. 24, pp. 1169–1175, 1976. · Zbl 0347.90063 |

[25] | Pardalos, P. M., and Rosen, J. B., Bounds for Solution Sets of Linear Complementarity Problems, Discrete Applied Mathematics, Vol. 17, pp. 255–261, 1987. · Zbl 0611.90094 |

[26] | L’Ecuyer, P., and Cote, S., Implementing a Random Number Package with Splitting Facilities, ACM Transactions on Mathematical Software, Vol. 17, pp. 98–111, 1991. · Zbl 0900.65008 |

[27] | Lin, Y. Y., and Pang, J. S., Iterative Methods for Large Convex Quadratic Programs, SIAM Journal on Control and Optimization, Vol. 25, pp. 383–411, 1987. · Zbl 0624.90083 |

[28] | Marsten, R. E., The Design of the XMP Linear Programming Library, ACM Transactions of Mathematical Software, Vol. 7, pp. 481–497, 1981. |

[29] | Ramarao, B., and Shetty, C. M., Application of Disjunctive Programming to the Linear Complementarity Problem, Naval Research Logistics Quarterly, Vol. 31, pp. 589–600, 1984. · Zbl 0559.90088 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.