Return to search
## Network models with generalized upper bound side constraints

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.0016 seconds