Optimization Online


A simple exact separation algorithm for 2-matching inequalities.

Julian Araoz (julian.araoz***at***upc.edu)
Elena Fernandez (e.fernandez***at***upc.edu)
Oscar Meza (meza***at***ldc.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.


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society