A new reformulation-linearization technique for bilinear programming problems.

*(English)*Zbl 0791.90056The authors present an efficient algorithm for solving jointly constrained bilinear programming problems [see F. A. Al-Khayyal and J. E. Falk, Math. Oper. Res. 8, 273-286 (1983; Zbl 0521.90087)]. In the proposed algorithm, they develop a new linearization technique for this type of problems and using this, they convert a bilinear programming problem into a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. The convergence of the algorithm is established and computational experience on some test problems is reported.

Reviewer: J.Parida (Rourkela)

##### MSC:

90C30 | Nonlinear programming |

90C26 | Nonconvex programming, global optimization |

90-08 | Computational methods for problems pertaining to operations research and mathematical programming |

##### Keywords:

global optimization; branch-and-bound; jointly constrained bilinear programming; linearization technique
PDF
BibTeX
XML
Cite

\textit{H. D. Sherali} and \textit{A. Alameddine}, J. Glob. Optim. 2, No. 4, 379--410 (1992; Zbl 0791.90056)

Full Text:
DOI

##### References:

[1] | Alameddine, A. R. (1990), A New Reformulation-Linearization Technique for the Bilinear Programming and Related Problems with Applications to Risk Management, Ph.D. Dissertation, Department of Industrial and Systems Engineering, Blacksburg, VA 24061. |

[2] | Al-Khayyal, F. A. and J. E.Falk (AF) (1983), Jointly Constrained Biconvex Programming, Mathematics of Operations Research 8, 273-286. · Zbl 0521.90087 |

[3] | Al-Khayyal, F. A. (1983), Jointly Constrained Bilinear Programming and Related Problems, Report, Industrial and Systems Engineering No. J-83-3, Georgia Institute of Technology, Atlanta, GA. |

[4] | Al-Khayyal, F. A. (1986), Linear Quadratic, and Bilinear Programming Approaches to the Linear Complementarity Problem, European Journal of Operational Research 24, 216-227. · Zbl 0581.90091 |

[5] | Al-Khayyal, F. A. (1990a), Jointly Constrained Bilinear Programs: An Overview, Journal of Computers and Mathematics with Applications 19(11), 53-62. · Zbl 0706.90074 |

[6] | Al-Khayyal, F. A. (1990b), Generalized Bilinear Programming, Part I: Models, Applications and Linear Programming Relaxation, European Journal of Operational Research, forthcoming. · Zbl 0784.90051 |

[7] | Al-Khayyal, F. A. and C.Larsen (AL) (1990), Global Minimization of a Quadratic Function Subject to a Bounded Mixed Integer Constraint Set, Annals of Operations Research 25, 169-180. · Zbl 0719.90050 |

[8] | Czochralska, I. (1982), Bilinear Programming, Applictines Mathematicae XVIII 3, 495-514. · Zbl 0506.90064 |

[9] | Falk, J. E. (1969), Lagrange Multipliers and Nonconvex Programs, SIAM Journal on Control 7(4), 534-545. · Zbl 0184.44404 |

[10] | Horst, R. (1976). An Algorithm for Nonconvex Programming Problems, Mathematical Programming 10, 312-321. · Zbl 0337.90062 |

[11] | Horst, R. (1986), A General Class of Branch and Bound Methods in Global Optimization with Some New Approaches for Concave Minimization, Journal of Optimization Theory and Applications 51(2), 271-291. · Zbl 0581.90073 |

[12] | Horst, R. and H.Tuy (1990), Global Optimization: Deterministic Approaches, Springer-Verlag, Berlin. · Zbl 0704.90057 |

[13] | Kalantari, B. and J. B.Rosen (1987), An Algorithm for Global Minimization of Linearly Constrained Concave Quadratic Functions, Mathematics of Operations Research, 12, 544-561. · Zbl 0638.90081 |

[14] | Konno, H. (1971) Bilinear Programming, Part I: An Algorithm for Solving Bilinear Programs, Technical Report No. 71-9, Operations Research House, Stanford University (Stanford, CA). |

[15] | Konno, H. (1971), Bilinear Programming, Part II: Applications of Bilinear Programming, Technical Report No. 71-10, Operations Research House, Stanford University (Stanford, CA). |

[16] | Konno, H. (1976a), A Cutting Plane Algorithm for Solving Bilinear Programs, Mathematical Programming 11, 14-27. · Zbl 0353.90069 |

[17] | Konno, H. (1976b), Maximization of a Convex Quadratic Function under Linear Constraints, Mathematical Programming 11, 117-127. · Zbl 0355.90052 |

[18] | Konno, H. and T. Kuno (KK) (1989), Generalized Linear Multiplicative and Fractional Programming, forthcoming. |

[19] | Muu, L. D. and W. Oettli (1990), Combined Branch-and-Bound and Cutting Plane Methods for Solving a Class of Nonlinear Programming Problems, forthcoming. · Zbl 0780.90088 |

[20] | Ritter, K. (1966) A Method for Solving Maximum Problems with a Nonconvex Quadratic Objective Function, Wahrscheinlichkeitstheorie 4, 340-351. · Zbl 0139.13105 |

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

[22] | Sherali, H. D. and W. P. Adams (1990b), A Hierarchy of Relaxations and Convex Hull Characterizations for Zero-One Mixed Integer Programming Problems, forthcoming. · Zbl 0712.90050 |

[23] | Sherali, H. D. and A. R. Alameddine (1990), An Explicit Characterization of the Convex Envelope of a Bivariate Bilinear Function over Special Polytopes, in Pardalos P. M. and J. B. Rosen (eds.), Annals of OR: Computational Methods in Global Optimization 25, 197-210. · Zbl 0723.90073 |

[24] | Sherali, H. D. and C. M.Shetty (SS) (1980), A Finitely Convergent Algorithm for Bilinear Progamming Problems Using Polar Cuts and Disjunctive Face Cuts, Mathematical Programming 19, 14-31. · Zbl 0436.90079 |

[25] | Sherali, H. D. and C. H.Tuncbilek (1991), A Global Optimization Algorithm for Polynomial Programming Problems Using a Reformulation-Linearization Technique, in Floudas, C. A. and P. M.Pardalos (eds.), Recent Advances in Global Optimization, Princeton University Press, Princeton, NJ, forthcoming. (Also, Journal of Global Optimization 2, 101-112 (1992).) · Zbl 0787.90088 |

[26] | Thieu, T. V. (1988), A Note on the Solution of Bilinear Problems by Reduction to Concave Minimization, Mathematical Programming 41, 249-260. · Zbl 0643.90054 |

[27] | Tuy, H. (1964), Concave Programming under Linear Constraints, Soviet Math. Doklady 5, 1437-1440. · Zbl 0132.40103 |

[28] | Vaish, H. and C. M.Shetty (1976), The Bilinear Programming Problem, Naval Research Logistics Quarterly 23, 303-309. · Zbl 0349.90071 |

[29] | Vaish, H. and C. M.Shetty (1977), A Cutting Plane Algorithm, for the Bilinear Programming Problem, Naval Research Logistics Quarterly 24, 83-94. · Zbl 0372.90082 |

[30] | Yajima, Y. and H. Konno (1989), Efficient Algorithms for Solving Rank Two and Rank Three Bilinear Programs, forthcoming. · Zbl 0748.90050 |

[31] | Zwart, P. B. (ZW) (1973), Nonlinear Programming: Counterexamples to Two Global Optimization Algorithms, Operations Research 21, 1260-1266. · Zbl 0274.90049 |

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.