Representing inverses in pure network flow optimization

DOI10.1016/0377-2217(86)90301-2MaRDI QIDQ1068691zbMATH OpenOpenAlexFDO

Authors Richard E. Rosenthal

Publication date 1986

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(86)90301-2

zbMATH Keywords

inverse-treepure network flow problemspecial structure

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10) Linear programming (90C05) Programming involving graphs or networks (90C35)

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.

Recommendations

• A network flow method for solving some inverse combinatorial optimization problems
• Design and Implementation of Data Structures for Generalized Networks
• Solving inverse spanning tree problems through network flow techniques
• scientific article; zbMATH DE number 1484312
• Combinatorial algorithms for inverse network flow problems

Cites work

• A network simplex method
• A Nonlinear Network Flow Algorithm for Maximization of Benefits in a Hydroelectric Power System
• An improved version of the out-of-kilter method and a comparative study of computer codes
• Augmented Threaded Index Method For Network Optimization
• Benefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm
• Enhancements Of Spanning Tree Labelling Procedures For Network Optimization
• Exceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3690676 (Why is no real title available?)
• scientific article; zbMATH DE number 3791941 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems
• Implementation and Computational Study on an In-Core, Out-of-Core Primal Network Code
• Inductive Proof of the Simplex Method
• Microdata file merging through large-scale network technology
• Optimal Capacity Scheduling—I
• Optimality and Computation of (σ, S) Policies in the Multi-Item Infinite Horizon Inventory Problem
• Testing of a large-scale network optimization program
• The factorization approach to large-scale linear programming

Cited in

(2)

• On the structure of the basis inverse for the transportation problem
• A survey of dynamic network flows

This page was built for publication: Representing inverses in pure network flow optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1068691)