Computational improvements to Benders decomposition for generalized fixed charge problems Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/qf85nf18j

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • A computationally efficient algorithm has been developed for determining exact or approximate solutions for large scale generalized fixed charge problems. This algorithm is based on a relaxation of the Benders decomposition procedure, combined with a linear mixed integer programming (MIP) algorithm specifically designed to solve the problem associated with Benders decomposition and a computationally improved generalized upper bounding (GUB) algorithm which solves a convex separable programming problem by generalized linear programming. A dynamic partitioning technique is defined and used to improve computational efficiency. All component algorithms have been theoretically and computationally integrated with the relaxed Benders algorithm for maximum efficiency for the generalized fixed charge problem. The research was directed toward the approximate solution of a particular class of large scale generalized fixed charge problems, and extensive computational results for problems of this type are given. As the size of the problem diminishes, the relaxations can be enforced, resulting in a classical Benders decomposition, but with special purpose sub-algorithms and improved convergence properties. Many of the results obtained apply to the sub-algorithms independently of the context in which they were developed. The procedure for solving the associated MIP is applicable to any linear 0/1 problem of Benders form, and the techniques developed for the linear program are applicable to any large scale generalized GUB implementation.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2010-07-22T15:47:27Z (GMT) No. of bitstreams: 1 RedactedBattilegaJohnAnthony1973.pdf: 2485185 bytes, checksum: 02dbe5188c36f70cb7fe7722ddec81b1 (MD5)
  • description.provenance : Submitted by Joe Nguyen (jnscanner@gmail.com) on 2010-07-22T01:19:47Z No. of bitstreams: 1 RedactedBattilegaJohnAnthony1973.pdf: 2485185 bytes, checksum: 02dbe5188c36f70cb7fe7722ddec81b1 (MD5)
  • description.provenance : Made available in DSpace on 2010-07-22T15:47:27Z (GMT). No. of bitstreams: 1 RedactedBattilegaJohnAnthony1973.pdf: 2485185 bytes, checksum: 02dbe5188c36f70cb7fe7722ddec81b1 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2010-07-22T15:44:02Z (GMT) No. of bitstreams: 1 RedactedBattilegaJohnAnthony1973.pdf: 2485185 bytes, checksum: 02dbe5188c36f70cb7fe7722ddec81b1 (MD5)

Relationships

In Administrative Set:
Last modified: 08/14/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items