Extracting embedded generalized networks from linear programming problems

DOI10.1007/BF01585656zbMath0574.90060OpenAlexW2003455391MaRDI QIDQ3693261

R. Kevin Wood, Gerald G. Brown, Richard D. McBride

Publication date: 1985

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585656

zbMATH Keywords

computational complexityapproximate solutionsheuristic algorithmsNP-completegeneralized networksComputational experiencebasis factorization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Linear programming (90C05) Boolean programming (90C09)

Related Items

Dynamic factorization in large-scale optimization, Layering strategies for creating exploitable structure in linear and integer programs, A network relaxation based enumeration algorithm for set partitioning, Use of hidden network structure in the set partitioning problem, The structure of bases in bicircular matroids, A survey of dynamic network flows, Detecting embedded pure network structures in LP problems, Future paths for integer programming and links to artificial intelligence, Heuristic methods and applications: A categorized survey

Cites Work

• Unnamed Item
• A good submatrix is hard to find
• Solving Generalized Networks
• Automatic identification of embedded network rows in large-scale optimization models
• Converting Linear Programs to Network Problems
• Automatic Identification of Generalized Upper Bounds in Large-Scale Optimization Models
• Node-Deletion Problems on Bipartite Graphs
• The simplex SON algorithm for LP/embedded network problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
• Analysis of mathematical programming problems prior to applying the simplex algorithm
• The factorization approach to large-scale linear programming
• Exceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
• Computer Solutions of the Traveling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem