An exact approach to the problem of extracting an embedded network matrix

DOI10.1016/j.cor.2011.01.003zbMath1210.90038OpenAlexW4299572240MaRDI QIDQ716336

Rosa M. V. Figueiredo, Martine Labbé, Cid Carvalho De Souza

Publication date: 28 April 2011

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.01.003

zbMATH Keywords

signed graphbranch-and-cutfacets of polyhedranetwork matrix

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10)

Related Items (3)

A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem ⋮ A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph ⋮ The maximum balanced subgraph of a signed graph: applications and solution approaches

Uses Software

• XPRESS

Cites Work

• A branch and cut solver for the maximum stable set problem
• Facets of the balanced (acyclic) induced subgraph polytope
• Signed graphs
• A class of facet producing graphs for vertex packing polyhedra
• A heuristic for finding embedded network structure in mathematical programmes
• Extracting pure network submatrices in linear programs using signed graphs.
• A good submatrix is hard to find
• Automatic identification of embedded network rows in large-scale optimization models
• Finding a Maximum Clique in an Arbitrary Graph
• Finding Embedded Network Rows in Linear Programs I. Extraction Heuristics
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• On the cut polytope
• On the facial structure of set packing polyhedra
• A branch-and-cut algorithm for the maximum cardinality stable set problem

This page was built for publication: An exact approach to the problem of extracting an embedded network matrix