Abstract
The Bilinear Programming Problem is a structured quadratic programming problem whose objective function is, in general, neither convex nor concave. Making use of the formal linearity of a dual formulation of the problem, we give a necessary and sufficient condition for optimality, and an algorithm to find an optimal solution.
Similar content being viewed by others
References
E. Balas, “Intersection Cuts — A new type of cutting planes for integer programming”,Operations Research 19 (1971) 19–39.
G. Gallo, “On Hoang Tui's concave programming algorithm”, Nota Scientifica S-76-1, Instituto di Scienze dell'Informazione, University of Pisa Italy (1975).
F. Glover, “Convexity cuts and cut search”,Operations Research 21 (1973) 123–134.
B. Grünbaum,Convex polytopes (Wiley, New York, 1967).
H. Konno, “Bilinear programming: Part I. Algorithm for solving bilinear programs”, Tech. Rept. No. 71-9, Stanford University, Stanford, CA (1971).
A. H. Land and S. Powell,Fortran codes for mathematical programming: linear, quadratic and discrete (Wiley, New York, 1973).
Hoang Tui, “Concave programming under linear constraints”,Doklady Akademii Nauk SSR 159 (1964) 32–35. [English translation:Soviet Mathematics 5 (1964) 1437–1440.]
P. B. Zwart, “Nonlinear programming: counterexamples to two global optimization algorithms”,Operations Research 21 (1973) 1260–1266.
Author information
Authors and Affiliations
Additional information
Research partially supported by the Office of Naval Research under Contract N00014-69-A-0200-1010 with the University of California.
Rights and permissions
About this article
Cite this article
Gallo, G., Ülkücü, A. Bilinear programming: An exact algorithm. Mathematical Programming 12, 173–194 (1977). https://doi.org/10.1007/BF01593787
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01593787