A heuristic algorithm for a network problem with variable upper bounds Academic Article uri icon


  • We present a heuristic algorithm for the solution of a network problem with variable upper bounds. This algorithm is motivated by the desire to exploit the special structure of the variable upper bound (VUB) constraints and to maintain as much of the characteristics of pure network problems as possible. Our solution technique for the VUB problem consists of solving two sequences of pure network problems. One sequence yields tighter lower bounds on the optimal objective value by considering the Lagrangean relaxation in which the VUB constraints are dualized. The second sequence yields upper bounds on the optimal value for the problem. This sequence is obtained by considering a reformulation of the VUB problem based on parametric changes in the variable upper bound. The algorithm has been tested on problems with as many as 1500 nodes, 6600 arcs, and 3000 VUB constraints. Computational experience with the solution of randomly generated fixedcharge network problems, capacitated warehouse location problems, and production smoothing problems is also reported. Copyright 1990 Wiley Periodicals, Inc., A Wiley Company

published proceedings

  • Networks

author list (cited authors)

  • Shetty, B.

citation count

  • 3

complete list of authors

  • Shetty, Bala

publication date

  • July 1990