Graduate Thesis Or Dissertation
 

A general linear optimization algorithm based upon labeling and factorizing of basic paths on RPM network

Öffentlich Deposited

Herunterladbarer Inhalt

PDF Herunterladen
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/0z709160v

Descriptions

Attribute NameValues
Creator
Abstract
  • A new method is developed for solving linear optimization problems based on the RPM network modeling technique which represents the primal and the corresponding dual models simultaneously upon a single graph. The network structure is used to eliminate the need for explicit logical variables and to provide a graphic tool in analyzing the problem. The new algorithm iterates through a finite number of basic solutions working towards optimality (primal) or towards feasibility (dual). At each iteration a set of critical constraints and basic structural variables are identified to form the current basic path network. A solution for the basic variables is obtained through factorization of the basis and used to update the nonbasic network. If the Kuhn-Tucker conditions are not satisfied, the method proceeds with the next iteration unless an unbounded or infeasible solution is encountered. Under the new scheme, the original data remains unchanged throughout the optimization procedure and round-off errors can be kept to a minimum. Furthermore, the basic paths representation used in factorization reduces computer core requirement and permits direct - addressing of pertinent non-basic node data on disk storage. These features are especially appealing in solving large-scale problems even on limited computer hardware. Since the size of the basis is never greater than the size of the basis required by simplex-type algorithms, the new scheme has an advantageous memory storage requirement. Any basic solution (not necessarily optimum or feasible) can be used as a starting point and multipivoting can accelerate the optimization process. In general, the number of iterations and the amount of operations depends on the sparsity of the constrained matrix and the complexity of the problem. Statistical data based on sample experimental results indicate that the new algorithm, on the average, requires less arithmetic operations and no more iterations to reach the final solution than the simplex-type algorithms.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Urheberrechts-Erklärung
Publisher
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

Beziehungen

Parents:

This work has no parents.

In Collection:

Artikel

Miniaturansicht Titel Hochladedatum Sichtbarkeit Aktionen
file details StavrakisGeorgeD1981.pdf 2017-10-19 Öffentlich Herunterladen