Abstract
This paper is concerned with the development of an algorithm for general bilinear programming problems. Such problems find numerous applications in economics and game theory, location theory, nonlinear multi-commodity network flows, dynamic assignment and production, and various risk management problems. The proposed approach develops a new Reformulation-Linearization Technique (RLT) for this problem, and imbeds it within a provably convergent branch-and-bound algorithm. The method first reformulates the problem by constructing a set of nonnegative variable factors using the problem constraints, and suitably multiplies combinations of these factors with the original problem constraints to generate additional valid nonlinear constraints. The resulting nonlinear program is subsequently linearized by defining a new set of variables, one for each nonlinear term. This “RLT” process yields a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. Various implementation schemes and constraint generation procedures are investigated for the purpose of further tightening the resulting linearization. The lower bound thus produced theoretically dominates, and practically is far tighter, than that obtained by using convex envelopes over hyper-rectangles. In fact, for some special cases, this process is shown to yield an exact linear programming representation. For the associated branch-and-bound algorithm, various admissible branching schemes are discussed, including one in which branching is performed by partitioning the intervals for only one set of variables x or y, whichever are fewer in number. Computational experience is provided to demonstrate the viability of the algorithm. For a large number of test problems from the literature, the initial bounding linear program itself solves the underlying bilinear programming problem.
Similar content being viewed by others
References
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.
Al-Khayyal, F. A. and J. E.Falk (AF) (1983), Jointly Constrained Biconvex Programming, Mathematics of Operations Research 8, 273–286.
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.
Al-Khayyal, F. A. (1986), Linear Quadratic, and Bilinear Programming Approaches to the Linear Complementarity Problem, European Journal of Operational Research 24, 216–227.
Al-Khayyal, F. A. (1990a), Jointly Constrained Bilinear Programs: An Overview, Journal of Computers and Mathematics with Applications 19(11), 53–62.
Al-Khayyal, F. A. (1990b), Generalized Bilinear Programming, Part I: Models, Applications and Linear Programming Relaxation, European Journal of Operational Research, forthcoming.
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.
Czochralska, I. (1982), Bilinear Programming, Applictines Mathematicae XVIII 3, 495–514.
Falk, J. E. (1969), Lagrange Multipliers and Nonconvex Programs, SIAM Journal on Control 7(4), 534–545.
Horst, R. (1976). An Algorithm for Nonconvex Programming Problems, Mathematical Programming 10, 312–321.
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.
Horst, R. and H.Tuy (1990), Global Optimization: Deterministic Approaches, Springer-Verlag, Berlin.
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.
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).
Konno, H. (1971), Bilinear Programming, Part II: Applications of Bilinear Programming, Technical Report No. 71–10, Operations Research House, Stanford University (Stanford, CA).
Konno, H. (1976a), A Cutting Plane Algorithm for Solving Bilinear Programs, Mathematical Programming 11, 14–27.
Konno, H. (1976b), Maximization of a Convex Quadratic Function under Linear Constraints, Mathematical Programming 11, 117–127.
Konno, H. and T. Kuno (KK) (1989), Generalized Linear Multiplicative and Fractional Programming, forthcoming.
Muu, L. D. and W. Oettli (1990), Combined Branch-and-Bound and Cutting Plane Methods for Solving a Class of Nonlinear Programming Problems, forthcoming.
Ritter, K. (1966) A Method for Solving Maximum Problems with a Nonconvex Quadratic Objective Function, Wahrscheinlichkeitstheorie 4, 340–351.
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.
Sherali, H. D. and W. P. Adams (1990b), A Hierarchy of Relaxations and Convex Hull Characterizations for Zero-One Mixed Integer Programming Problems, forthcoming.
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.
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.
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).)
Thieu, T. V. (1988), A Note on the Solution of Bilinear Problems by Reduction to Concave Minimization, Mathematical Programming 41, 249–260.
Tuy, H. (1964), Concave Programming under Linear Constraints, Soviet Math. Doklady 5, 1437–1440.
Vaish, H. and C. M.Shetty (1976), The Bilinear Programming Problem, Naval Research Logistics Quarterly 23, 303–309.
Vaish, H. and C. M.Shetty (1977), A Cutting Plane Algorithm, for the Bilinear Programming Problem, Naval Research Logistics Quarterly 24, 83–94.
Yajima, Y. and H. Konno (1989), Efficient Algorithms for Solving Rank Two and Rank Three Bilinear Programs, forthcoming.
Zwart, P. B. (ZW) (1973), Nonlinear Programming: Counterexamples to Two Global Optimization Algorithms, Operations Research 21, 1260–1266.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sherali, H.D., Alameddine, A. A new reformulation-linearization technique for bilinear programming problems. J Glob Optim 2, 379–410 (1992). https://doi.org/10.1007/BF00122429
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00122429