Title page for ETD etd-04262001-094818


Type of Document Dissertation
Author Fraticelli, Barbara M. P.
Author's Email Address barbf@vt.edu
URN etd-04262001-094818
Title Semidefinite Cuts and Partial Convexification Techniques with Applications to Continuous Nonconvex Optimization, Stochastic Integer Programming, and Facility Layout Problems
Degree PhD
Department Industrial and Systems Engineering
Advisory Committee
Advisor Name Title
Sherali, Hanif D. Committee Chair
Bish, Ebru K. Committee Member
Herdman, Terry L. Committee Member
Koelling, Charles Patrick Committee Member
Sarin, Subhash C. Committee Member
Keywords
  • semidefinite programming (SDP)
  • facility layout problem (FLP)
  • mixed-integer programming
  • disjunctive models.
  • Reformulation-Linearization Technique (RLT)
  • stochastic programming
Date of Defense 2001-04-06
Availability unrestricted
Abstract
This dissertation develops efficient solution techniques for general and problem-specific applications within nonconvex optimization, exploiting the constructs of the Reformulation-Linearization Technique (RLT). We begin by developing a technique to enhance general problems in nonconvex optimization through the use of a new class of RLT cuts, called semidefinite cuts. While these cuts are valid for any general problem for which RLT is applicable, we demonstrate their effectiveness in optimizing a nonconvex quadratic objective function over a simplex. Computational results indicate that on average, the semidefinite cuts have reduced the number of nodes in the branch-and-bound tree by a factor of 37.6, while decreasing solution time by a factor of 3.4. The semidefinite cuts have also led to a significant reduction in the optimality gap at termination, in some cases producing optimal solutions for problems that could not be solved using RLT alone.

We then narrow our focus to the class of mixed-integer programming (MIP) problems, and develop a modification of Benders’ decomposition method using concepts from RLT and lift-and-project cuts. This method is particularly motivated by the class of two-stage stochastic programs with integer recourse. The key idea is to design an RLT or lift-and-project cutting plane scheme for solving the subproblems where the cuts generated have right-hand sides that are functions of the first-stage variables. An illustrative example is provided to elucidate the proposed approach. The focus is on developing a first comprehensive finitely convergent extension of Benders’ methodology for problems having 0-1 mixed-integer subproblems.

We next address a specific challenging MIP application known as the facility layout problem, and we significantly improve its formulation through outer-linearization techniques and concepts from disjunctive programming. The enhancements produce a substantial increase in the accuracy of the layout produced, while at the same time, providing a dramatic reduction in computational effort. Overall, the maximum error in department size was reduced from about 6% to nearly zero, while solution time decreased by a factor of 110. Previously unsolved test problems from the literature that had defied even approximate solution methods have been solved to exact optimality using our proposed approach.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  fraticelli_dissertation.pdf 773.24 Kb 00:03:34 00:01:50 00:01:36 00:00:48 00:00:04

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

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