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

DOI10.1016/J.COR.2011.01.003MaRDI QIDQ716336zbMATH OpenOpenAlexFDO

Authors Rosa 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)

Recommendations

• Extracting pure network submatrices in linear programs using signed graphs.
• Finding Embedded Network Rows in Linear Programs I. Extraction Heuristics
• Extracting embedded generalized networks from linear programming problems
• Detecting embedded pure network structures in LP problems
• Décomposition en matrices graphiques de matrices en $\lbrace 0, 1, -1\rbrace $ : application à la résolution de programmes linéaires entiers

Cites work

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

Cited in

(5)

• The maximum balanced subgraph of a signed graph: applications and solution approaches
• scientific article; zbMATH DE number 3896660 (Why is no real title available?)
• 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
• Extracting pure network submatrices in linear programs using signed graphs.

Describes a project that uses

Uses Software

• XPRESS

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

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