caa a22 4500 469067918 CHVBK 20180323132913.0 cr unu---uuuuu 170328e19921201xx s 000 0 eng 10.1007/BF00122429 doi (NATIONALLICENCE)springer-10.1007/BF00122429 A new reformulation-linearization technique for bilinear programming problems [Elektronische Daten] [Hanif Sherali, Amine Alameddine] 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. Kluwer Academic Publishers, 1992 Bilinear programming nationallicence nonconvex programming nationallicence global optimization nationallicence branch-and-bound nationallicence reformulation-linearization technique nationallicence Sherali Hanif Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, 24061-0118, Blacksburg, VA, U.S.A. aut Alameddine Amine Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, 24061-0118, Blacksburg, VA, U.S.A. aut Journal of Global Optimization Kluwer Academic Publishers 2/4(1992-12-01), 379-410 0925-5001 2:4<379 1992 2 10898 https://doi.org/10.1007/BF00122429 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00122429 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Sherali Hanif Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, 24061-0118, Blacksburg, VA, U.S.A aut NATIONALLICENCE 700 1- Alameddine Amine Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, 24061-0118, Blacksburg, VA, U.S.A aut NATIONALLICENCE 773 0- Journal of Global Optimization Kluwer Academic Publishers 2/4(1992-12-01), 379-410 0925-5001 2:4<379 1992 2 10898 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer