Representing inverses in pure network flow optimization
type: Item
instance of: scholarly article
title: Representing inverses in pure network flow optimization
zbMATH Open document ID: 0582.90032
DOI: 10.1016/0377-2217(86)90301-2
author: Richard E. Rosenthal
published in: European Journal of Operational Research
publication date: 1986-01-01T00:00:00Z
review text: A basis for a pure network flow problem always exhibits special structure, whose exploitation has led to the development of extremely efficient network optimization software. The backbone of these programs is a data structure which represents the basis as a tree and is used to perform the linear algebraic steps required for optimization. We demonstrate that the basis inverse also possesses a special structure which we call the inverse-tree. We develop a data structure to represent the inverse tree, and we show that it obeys a symmetric relationship with the basis-tree data structure. (The predecessor function of the inverse- tree is the preorder link function of the basis-tree and vice versa). We develop efficient computational procedures for exploiting these results and show that using the inverse-tree requires computation of the same order as the basis-tree.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 3932751
zbMATH Keywords: pure network flow problem
zbMATH Keywords: special structure
zbMATH Keywords: inverse-tree
MaRDI profile type: Publication
full work available at URL: 0377-2217(86)90301-2
OpenAlex ID: W1986005130
cites work: Enhancements Of Spanning Tree Labelling Procedures For Network Optimization
cites work: An improved version of the out-of-kilter method and a comparative study of computer codes
cites work: Microdata file merging through large-scale network technology
cites work: Exceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
cites work: A network simplex method
cites work: Q3844775
cites work: Inductive Proof of the Simplex Method
cites work: Q5514188
cites work: Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems
cites work: Augmented Threaded Index Method For Network Optimization
cites work: Q3885184
cites work: Optimality and Computation of (σ, S) Policies in the Multi-Item Infinite Horizon Inventory Problem
cites work: Q3968758
cites work: Implementation and Computational Study on an In-Core, Out-of-Core Primal Network Code
cites work: The factorization approach to large-scale linear programming
cites work: Testing of a large-scale network optimization program
cites work: A Nonlinear Network Flow Algorithm for Maximization of Benefits in a Hydroelectric Power System
cites work: Benefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm
cites work: Optimal Capacity Scheduling—I
description: scientific article; zbMATH DE number 3932751