Network models with generalized upper bound side constraints Public Deposited

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

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • The objective of this thesis is to develop and computationally test a new algorithm for the class of network models with generalized upper bound (GUB) side constraints. Various algorithms have been developed to solve the network with arbitrary side constraints problem; however, no algorithm that exploits the special structure of the GUB side constraints previously existed. The proposed algorithm solves the network with GUB side constraints problem using two sequences of problems. One sequence yields a lower bound on the optimal value for the problem by using a Lagrangean relaxation based on relaxing copies of some subset of the original variables. This is achieved by first solving a pure network subproblem and then solving a set of single constraint bounded variable linear programs. Because only the cost coefficients change from one pure network subproblem to another, the optimal solution for one subproblem is at least feasible, if not optimal, for the next pure network subproblem. The second sequence yields an upper bound on the optimal value by using a decomposition of the problem based on changes in the capacity vector. Solving for the decomposed problem corresponds to solving for pure network subproblems that have undergone changes in lower and/or upper bounds. Recently developed reoptimization techniques are incorporated in the algorithm to find an initial (artificial) feasible solution to the pure network subproblem. A program is developed for solving the network with GUB side constraints problem by using the relaxation and decomposition techniques. The algorithm has been tested on problems with up to 200 nodes, 2000 arcs and 100 GUB constraints. Computational experience indicates that the upper bound procedure seems to perform well; however, the lower bound procedure has a fairly slow convergence rate. It also indicates that the lower bound step size, the initial lower bound value, and the lower and upper bound iteration strategies have a significant effect on the convergence rate of the lower bound algorithm.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
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 2013-04-01T18:03:05Z (GMT) No. of bitstreams: 1 BolouriMaryam1990.pdf: 7244725 bytes, checksum: c3b59b75ce9de1f4432e90dcc4809c5f (MD5)
  • description.provenance : Submitted by Kevin Martin (martikev@onid.orst.edu) on 2013-03-29T21:07:11Z No. of bitstreams: 1 BolouriMaryam1990.pdf: 7244725 bytes, checksum: c3b59b75ce9de1f4432e90dcc4809c5f (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-04-02T17:41:19Z (GMT) No. of bitstreams: 1 BolouriMaryam1990.pdf: 7350978 bytes, checksum: 19417209ba39732f32ef1606ce7a1318 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-04-03T20:01:47Z (GMT) No. of bitstreams: 1 BolouriMaryam1990.pdf: 7350978 bytes, checksum: 19417209ba39732f32ef1606ce7a1318 (MD5)
  • description.provenance : Submitted by Kevin Martin (martikev@onid.orst.edu) on 2013-04-02T16:49:06Z No. of bitstreams: 1 BolouriMaryam1990.pdf: 7350978 bytes, checksum: 19417209ba39732f32ef1606ce7a1318 (MD5)
  • description.provenance : Made available in DSpace on 2013-04-03T20:01:47Z (GMT). No. of bitstreams: 1 BolouriMaryam1990.pdf: 7350978 bytes, checksum: 19417209ba39732f32ef1606ce7a1318 (MD5) Previous issue date: 1989-07-27
  • description.provenance : Rejected by Patricia Black(patricia.black@oregonstate.edu), reason: Replace file on 2013-04-02T15:29:40Z (GMT)

Relationships

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

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items