Separating multi-oddity constrained shortest circuits over the polytope of stable multisets.

DOI10.1016/J.ORL.2003.05.001MaRDI QIDQ1417599zbMATH OpenOpenAlexFDO

Authors Eddie Cheng, Sven De Vries

Publication date 5 January 2004

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2003.05.001

zbMATH Keywords

efficient separation algorithmodd valued odd cycle inequalitystable multiset problemstable set problem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Programming involving graphs or networks (90C35)

Review text

The stable multiset problem was introduced by \textit{A. Koster} and \textit{A. Zymolka} [Math. Methods Oper. Res. 56, 45--65 (2002; Zbl 1023.90086)] as a generalization of the maximum stable set problem (known to be NP-hard). An efficient separation algorithm for the stable multiset problem is presented.

Recommendations

• On cycles and the stable multi-set polytope
• Stable multi-sets
• Faster separation of 1-wheel inequalities by graph products
• Separation problems for the stable set polytope
• Antiweb-wheel inequalities and their separation problems over the stable set polytopes

Cites work

• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Antiweb-wheel inequalities and their separation problems over the stable set polytopes
• Design and Implementation of an Interactive Optimization System for Telephone Network Planning
• Geometric algorithms and combinatorial optimization
• Stable multi-sets
• Weakly bipartite graphs and the max-cut problem
• Wheel inequalities for stable set polytopes

Cited in

(4)

• Antiweb-wheel inequalities and their separation problems over the stable set polytopes
• On cycles and the stable multi-set polytope
• Remarks on ‘equivalence of stability concepts for discrete time-varying systems’
• Computing cyclic invariants for molecular graphs

This page was built for publication: Separating multi-oddity constrained shortest circuits over the polytope of stable multisets.

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