Extracting embedded generalized networks from linear programming problems

DOI10.1007/BF01585656MaRDI QIDQ3693261zbMATH OpenOpenAlexFDO

Authors Gerald G. Brown, R. Kevin Wood, 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 solutionsNP-completeheuristic algorithmsgeneralized networksComputational experiencebasis factorization

Mathematics Subject Classification ID

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

Recommendations

• Solving embedded generalized network problems
• Finding Embedded Network Rows in Linear Programs I. Extraction Heuristics
• Detecting embedded pure network structures in LP problems
• On the simplex algorithm for networks and generalized networks
• The structure of bases in bicircular matroids

Cites work

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

Cited in

(16)

• Detecting embedded pure network structures in LP problems
• Use of hidden network structure in the set partitioning problem
• Solving embedded generalized network problems
• Dynamic factorization in large-scale optimization
• Future paths for integer programming and links to artificial intelligence
• Layering strategies for creating exploitable structure in linear and integer programs
• A network relaxation based enumeration algorithm for set partitioning
• Heuristic methods and applications: A categorized survey
• A heuristic for finding embedded network structure in mathematical programmes
• Finding Embedded Network Rows in Linear Programs I. Extraction Heuristics
• The structure of bases in bicircular matroids
• A survey of dynamic network flows
• On the complexity of recognizing a class of generalized networks
• An exact approach to the problem of extracting an embedded network matrix
• scientific article; zbMATH DE number 60242 (Why is no real title available?)
• Extracting pure network submatrices in linear programs using signed graphs.

This page was built for publication: Extracting embedded generalized networks from linear programming problems

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