Extracting embedded generalized networks from linear programming problems

DOI10.1007/BF01585656zbMATH Open0574.90060OpenAlexW2003455391MaRDI QIDQ3693261FDOQ3693261

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

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

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)

Cites Work

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

Cited In (16)

• Use of hidden network structure in the set partitioning problem
• Detecting embedded pure network structures in LP problems
• 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
• Title not available (Why is that?)
• 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)