Optimization Online


A simplex method for uncapacitated pure-supply infinite network flow problems

Christopher T. Ryan (chris.ryan***at***chicagobooth.edu)
Robert L. Smith (rlsmith***at***umich.edu)
Marina A. Epelman (mepelman***at***umich.edu)

Abstract: We provide a simplex algorithm for a structured class of uncapacitated countably-infinite network flow problems. Previous efforts required explicit capacities on arcs with uniformity properties that facilitate duality arguments. By contrast, this paper takes a ``primal'' approach by devising a simplex method that provably converges to optimal value using arguments based on convergence of spanning trees and nonnegativity of reduced costs. This allows for removal of explicit capacity bounds. The method also converges, on a subsequence, to an extremal optimal solution. Our method is tailored to our problem setting --- acyclic networks with nodes of only nonnegative supplies (or, alternatively, only demands). The necessary structure can be found in a variety of applied settings not amenable to existing methods including nonstationary infinite-horizon dynamic programming. A finite implementation of our simplex algorithm is provided for the infinite horizon dynamic lot sizing problem under linear costs.

Keywords: network simplex method, infinite networks, duality

Category 1: Infinite Dimensional Optimization

Category 2: Network Optimization


Download: [PDF]

Entry Submitted: 07/05/2017
Entry Accepted: 07/05/2017
Entry Last Modified: 07/06/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society