Automatic identification of embedded network rows in large-scale optimization models

DOI10.1007/BF02591728zbMath0532.90076OpenAlexW2073042128MaRDI QIDQ3315283

Gerald G. Brown, William G. Wright

Publication date: 1984

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

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

zbMATH Keywords

large-scale optimizationheuristic algorithmspolynomial boundednessgeneralized upper boundsNP- hardnessbasis factorizationexploitation of special structureidentification of embedded network rowsmaximum-size embedded pure network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Mixed integer programming (90C11)

Related Items

Dynamic factorization in large-scale optimization ⋮ A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem ⋮ A network relaxation based enumeration algorithm for set partitioning ⋮ Use of hidden network structure in the set partitioning problem ⋮ A survey of dynamic network flows ⋮ Extracting pure network submatrices in linear programs using signed graphs. ⋮ The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs ⋮ An exact approach to the problem of extracting an embedded network matrix ⋮ A heuristic for finding embedded network structure in mathematical programmes ⋮ Detecting embedded pure network structures in LP problems ⋮ The practical conversion of linear programmes to network flow models ⋮ Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs ⋮ Extracting embedded generalized networks from linear programming problems

Cites Work

• Unnamed Item
• Generalized upper bounding techniques
• Combinatorial Optimization: What is the State of the Art
• Converting Linear Programs to Network Problems
• Automatic Identification of Generalized Upper Bounds in Large-Scale Optimization Models
• Determining GUB sets via an invert agenda algorithm
• Analysis of mathematical programming problems prior to applying the simplex algorithm
• The factorization approach to large-scale linear programming