A new reformulation-linearization technique for the bilinear programming and related problems, with applications to risk management

Abstract

This research is primarily concerned with the development of a new algorithm for the general Bilinear Programming Problem (BlP). BLP's are a class of nonlinear, non convex problems that belong to a higher class known as Biconvex Programming Problems (BCP). These problems find numerous applications in engineering, industrial, and management environments. The new algorithm develops a novel Reformulation-Linearization Technique (RlT) that uses an enumeration of variable factors to multiply constraints, and uses constraints to multiply constraints, to generate new nonlinear constraints which are subsequently linearized by defining new variables. The motivation is to transform the nonconvex bilinear problem into a lower bounding linear program that closely approximates the (partial) convex hull of feasible solutions to the problem. when the objective function is accommodated into the constraints through an auxiliary variable. This is equivalent to implicitly constructing tight approximations for the convex envelope of the objective function. The characteristic transformation induced by the Rl T therefore intrinsically yields enhanced lower bounds for use in a branch-and-bound procedure. In particular, we show that this technique actually constructs the exact convex hull representation for special (triangular and quadrilateral) polytopes in R². Our results therefore generalize the convex envelope construction process over rectangular polytopes as done by AI-Khayyal and Falk [1983), and our approach significantly enhances the lower bounding capability of the underlying linear approximation, over that of the latter method.