Decomposition methods for solving a class of nonconvex programming problems dealing with bilinear and quadratic functions. (English) Zbl 0834.90101

Summary: We develop convergent decomposition branch-and-bound algorithms for solving a class of bilinear programming problems. As an application of the proposed method, we apply it to quadratic programs with a few negative eigenvalues, and to a class of mixed integer programming problems.


90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C11 Mixed integer programming
Full Text: DOI


[1] F.A. Al-Khayyal and J.E. Falk, ?Jointly constrained biconvex programming,? Mathematics of Operations Research, Vol. 8 pp. 273-286, 1983. · Zbl 0521.90087
[2] R. Horst and H. Tuy, ?Global Optimization: Deterministic Approaches,? 2 edition Berlin, New York: Springer-Verlag, 1993. · Zbl 0704.90057
[3] H. Konno, ?A cutting plane algorithm for solving bilinear programs,? Mathematical Programming, Vol. 11, pp. 14-27, 1976. · Zbl 0353.90069
[4] L.D. Muu and W. Oettli, ?A method for minimizing a convex?concave function over a convex set,? J. of Optimization Theory and Applications, Vol. 70 pp. 337-384, 1991. · Zbl 0743.90101
[5] L.D. Muu and W. Oettli. ?Combined branch and bound and cutting plane methods for solving a class of nonlinear programming problems,? J. of Global Optimization, Vol. 3, pp. 377-391, 1993. · Zbl 0780.90088
[6] L.D. Muu and B.T. Tam, ?Efficient methods for solving certain bilinear programming problem,? to appear in Acta Mathematica Vietnamica. · Zbl 0889.90139
[7] P.M. Pardalos and J.B. Rosen, ?Constrained global optimization: Algorithms and applications,? in G. Goos and J. Hartmans, editors, Lecture Notes in Computer Science, number 268. Berlin: Springer-Verlag, 1987. · Zbl 0638.90064
[8] P.M. Pardalos and S.A. Vavasis, ?Quadratic programming with one negative eigenvalue is NP-hard,? J. of Global Optimization, Vol. 21, pp. 843-855, 1991.
[9] A.T. Phillips and J.B. Rosen, ?A parallel algorithm for constrained concave quadratic global minimization,? Mathematical Programming, Vol. 42, pp. 412-448, 1988. · Zbl 0665.90071
[10] T.Q. Phong, L.T.H. An, and Pham D. Tao, ?On globally solving linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method,? (submitted). · Zbl 0857.90098
[11] H.D. Sherali and A. Alameddine, ?A new reformulation?linearization technique for bilinear programming problems,? J. of Global Optimization, Vol. 2, pp. 379-410, 1992. · Zbl 0791.90056
[12] H.D. Sherali and C.M. Shetty, ?A finitely convergent algorithm for bilinear programming problem using polar cuts and disjunctive face cuts,? Mathematical Programming, Vol. 19, pp. 379-410, 1980. · Zbl 0436.90079
[13] Pham D. Tao ?Un algorithme pour la résolution du programme linéaire général,? RAIRO-Recherche opérationnelle, Vol. 25, pp. 183-201, 1991.
[14] T.V. Thieu, ?Relationship between bilinear programming and concave programming,? Acta Mathematica Vietnamica, Vol. 2, pp. 106-113 (1980). · Zbl 0486.90061
[15] N. V. Thoai and H. Tuy, ?Convergent algorithms for minimizing a concave function,? Mathematics of Operations Research, Vol. 5 pp. 556-566 (1980). · Zbl 0472.90054
[16] H. Vaish and C.M. Shetty, ?The bilinear programming problems,? Naval Res. Log. Quar., Vol. 23, pp. 303-319, 1976. · Zbl 0349.90071
[17] H. Vaish and C.M. Shetty, ?A cutting plane algorithm for bilinear programming problems,? Naval Res. Log. Quar., Vol. 24, pp. 83-94, 1976. · Zbl 0372.90082
[18] Y. Yajima and H. Konno, ?Efficient algorithm for solving rank two and rank three bilinear programming problems,? J. of Global Optimization, Vol. 1, pp. 155-173, 1991. · Zbl 0748.90050
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.