A computational analysis of LCP methods for bilinear and concave quadratic programming

• Tipo: Artigo em Revista Científica Internacional
• Data: 1991

Autores

J. Júdice (Autor) Outra; Ana Maria Faustino (Autor) FEUP

Revista

Título: Computers and Operations Research

Nº 18

Páginas: 645-654

ISSN: 0305-0548

Editora: Elsevier

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Outras ciências da engenharia e tecnologias

Outras Informações

Resumo (PT): It is discussed the use of a Sequential LCP (SLCP) algorithm for finding a global minimum of a Bilinear Programming problem (BLP) or a Concave Quadratic Program (CQP). The algorithm consists of solving a sequence of Linear Complementarity Problems (LCP). A Branch-and-Bound method is also considered in this study. This algorithm is based on the reformulation of a BLP into a LCP with a linear function to minimize. Computational experience with small and medium scale BLPs and CQPs indicates that the SLCP algorithm is quite efficient to find a global minimum (or at least a solution that is quite near the optimum), but it is in general unable to establish that such a solution has been found. An algorithm to f~nd a lower-bound for the BLP can overcome this drawback in some cases. Furthermore the SLCP algorithm is shown to be robust and compares favorably with the Branch-and-Bound method and another alternative technique.

Abstract (EN): It is discussed the use of a Sequential LCP (SLCP) algorithm for finding a global minimum of a Bilinear Programming problem (BLP) or a Concave Quadratic Program (CQP). The algorithm consists of solving a sequence of Linear Complementarity Problems (LCP). A Branch-and-Bound method is also considered in this study. This algorithm is based on the reformulation of a BLP into a LCP with a linear function to minimize. Computational experience with small and medium scale BLPs and CQPs indicates that the SLCP algorithm is quite efficient to find a global minimum (or at least a solution that is quite near the optimum), but it is in general unable to establish that such a solution has been found. An algorithm to f~nd a lower-bound for the BLP can overcome this drawback in some cases. Furthermore the SLCP algorithm is shown to be robust and compares favorably with the Branch-and-Bound method and another alternative technique.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 10