Show simple item record

dc.contributor.authorFraticelli, Barbara M. P.en
dc.date.accessioned2014-03-14T20:10:51Zen
dc.date.available2014-03-14T20:10:51Zen
dc.date.issued2001-04-06en
dc.identifier.otheretd-04262001-094818en
dc.identifier.urihttp://hdl.handle.net/10919/27293en
dc.description.abstractThis 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.en
dc.publisherVirginia Techen
dc.relation.haspartfraticelli_dissertation.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectsemidefinite programming (SDP)en
dc.subjectfacility layout problem (FLP)en
dc.subjectmixed-integer programmingen
dc.subjectdisjunctive models.en
dc.subjectReformulation-Linearization Technique (RLT)en
dc.subjectstochastic programmingen
dc.titleSemidefinite Cuts and Partial Convexification Techniques with Applications to Continuous Nonconvex Optimization, Stochastic Integer Programming, and Facility Layout Problemsen
dc.typeDissertationen
dc.contributor.departmentIndustrial and Systems Engineeringen
dc.description.degreePh. D.en
thesis.degree.namePh. D.en
thesis.degree.leveldoctoralen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.disciplineIndustrial and Systems Engineeringen
dc.contributor.committeechairSherali, Hanif D.en
dc.contributor.committeememberSarin, Subhash C.en
dc.contributor.committeememberBish, Ebru K.en
dc.contributor.committeememberHerdman, Terry L.en
dc.contributor.committeememberKoelling, C. Patricken
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-04262001-094818/en
dc.date.sdate2001-04-26en
dc.date.rdate2002-04-26en
dc.date.adate2001-04-26en


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record