Jointly constrained bilinear programs and related problems: An overview (Q918873)

This paper is an overview of some of the theoretical and computational aspects (particularly cutting-plane and branch and bound algorithms) of certain bilinear programs, that is, problems of the form: minimize \(f(x)+x^ Ty+g(y)\) subject to (x,y)\(\in S\cap \Omega\), where f and g are convex \(S\cap \Omega \subset R^{2n}\), the nonempty set S is closed and convex and \(\Omega =\{(x,y):\) \(1\leq x\leq L\), \(m\leq y\leq M\}\) is a compact rectangle. S may be defined by functional constraints \(h_ i(x,y)\leq 0\). Also problems are considered in the form: minimize \(c^ Tx+x^ TAy+d^ Ty\) subject to \(x\in X\), \(y\in Y\), where c and d are given vectors, A is a rectangular matrix and X and Y are given polyhedra. Some suggestions for future research are made. An extensive bibliography is given.