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. / Graduation date: 1990
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/37991 |
| Date | 27 July 1989 |
| Creators | Bolouri, Maryam |
| Contributors | Arthur, Jeffrey L. |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0021 seconds