Type of Document	Dissertation
Author	Alameddine, Amine R.
URN	etd-10192005-113325
Title	A new reformulation-linearization technique for the bilinear programming and related problems, with applications to risk management
Degree	PhD
Department	Industrial and Systems Engineering
Advisory Committee	Advisor Name Title Glickman, Theodore S. Committee Chair Sherali, Hanif D. Committee Chair Koelling, Charles Patrick Committee Member Sarin, Subhash C. Committee Member Sumichrast, Robert T. Committee Member
Keywords	Risk management. Linear programming.
Date of Defense	1990-10-23
Availability	restricted
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 R2. 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.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access  LD5655.V856_1990.A523.pdf 6.78 Mb 00:31:22 00:16:07 00:14:06 00:07:03 00:00:36 next to an author's name indicates that all files or directories associated with their ETD are accessible from the Virginia Tech campus network only.

If you have questions or technical problems, please Contact DLA.