A simple exact separation algorithm for 2-matching inequalities.
Julian Araoz (julian.araozupc.edu)
Abstract: In this work we present an exact separation algorithm for the so called co-circuit inequalities, otherwise known as parity or 2-matching inequalities. The algorithm is quite simple since it operates on the tree of min-cuts of the support graph of the solution to separate, relative to an ad hoc capacity vector. The order of our algorithm is O(|V|^4) which is considerably smaller to that of other algorithms proposed in the literature, which is O((|V|+|E|)^4).
Keywords: Separation algorithms, complexity.
Category 1: Combinatorial Optimization
Citation: Technical University of Catalonia. Jordi Girona 1-3, 08034 Barcelona, Spain. November, 2007.
Entry Submitted: 11/07/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|