A simple exact separation algorithm for 2-matching inequalities.

Julian Araoz (julian.araozupc.edu)
Elena Fernandez (e.fernandezupc.edu)
Oscar Meza (mezaldc.usb.ve)

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.

Download:

Entry Submitted: 11/07/2007
Entry Accepted: 11/08/2007
Entry Last Modified: 12/03/2007

Modify/Update this entry