Title page for ETD etd-10192005-113325
|Type of Document
||Alameddine, Amine R.
||A new reformulation-linearization technique for the bilinear programming and related problems, with applications to risk management
||Industrial and Systems Engineering
|Glickman, Theodore S.
|Sherali, Hanif D.
|Koelling, Charles Patrick
|Sarin, Subhash C.
|Sumichrast, Robert T.
- Risk management.
- Linear programming.
|Date of Defense
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.
|| Approximate Download Time
| 28.8 Modem
|| 56K Modem
|| ISDN (64 Kb)
|| ISDN (128 Kb)
|| Higher-speed Access
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.