A faster exact separation algorithm for blossom inequalities

Management Science

Text available via DOI:

https://doi.org/10.1007/978-3-540-25960-2_15
Final published version

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed)

Published

Standard

A faster exact separation algorithm for blossom inequalities. / Letchford, A N; Reinelt, G; Theis, D O.
Integer Programming and Combinatorial Optimization : Proceedings of the 10th International IPCO Conference. ed. / George Nemhauser; Daniel Bienstock. Berlin: Springer, 2004. p. 19-52 (Lecture Notes in Computer Science; Vol. 3064).

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed)

Harvard

Letchford, AN, Reinelt, G & Theis, DO 2004, A faster exact separation algorithm for blossom inequalities. in G Nemhauser & D Bienstock (eds), Integer Programming and Combinatorial Optimization : Proceedings of the 10th International IPCO Conference. Lecture Notes in Computer Science, vol. 3064, Springer, Berlin, pp. 19-52, 10th International IPCO Conference, New York, United States, 7/06/04. https://doi.org/10.1007/978-3-540-25960-2_15

APA

Letchford, A. N., Reinelt, G., & Theis, D. O. (2004). A faster exact separation algorithm for blossom inequalities. In G. Nemhauser, & D. Bienstock (Eds.), Integer Programming and Combinatorial Optimization : Proceedings of the 10th International IPCO Conference (pp. 19-52). (Lecture Notes in Computer Science; Vol. 3064). Springer. https://doi.org/10.1007/978-3-540-25960-2_15

Vancouver

Letchford AN, Reinelt G, Theis DO. A faster exact separation algorithm for blossom inequalities. In Nemhauser G, Bienstock D, editors, Integer Programming and Combinatorial Optimization : Proceedings of the 10th International IPCO Conference. Berlin: Springer. 2004. p. 19-52. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-25960-2_15

Author

Letchford, A N ; Reinelt, G ; Theis, D O. / A faster exact separation algorithm for blossom inequalities. Integer Programming and Combinatorial Optimization : Proceedings of the 10th International IPCO Conference. editor / George Nemhauser ; Daniel Bienstock. Berlin : Springer, 2004. pp. 19-52 (Lecture Notes in Computer Science).

Bibtex

@inbook{746bb393d35e467bb1b1175a3d9c17cc,

title = "A faster exact separation algorithm for blossom inequalities",

abstract = "In 1982, Padberg and Rao gave a polynomial-time separation algorithm for b-matching polyhedra. The current best known implementations of their separation algorithm run in O(|V|^2|E| log(|V|^2/|E|)) time when there are no edge capacities, but in O(|V||E|^2 log(|V|^2/|E|)) time when capacities are present. We propose a new exact separation algorithm for the capacitated case which has the same running time as for the uncapacitated case. For the sake of brevity, however, we will restrict our introduction to the case of perfect 1-capacitated b-matchings, which includes, for example, the separation problem for perfect 2-matchings. As well as being faster than the Padberg-Rao approach, our new algorithm is simpler and easier to implement.",

author = "Letchford, {A N} and G Reinelt and Theis, {D O}",

note = "The full version of this paper appeared as: A.N. Letchford, G. Reinelt & D.O. Theis (2008) Odd minimum cut-sets and b-matchings revisited. SIAM J. Discr. Math., 22(4), 1480-1487.; 10th International IPCO Conference ; Conference date: 07-06-2004 Through 11-06-2004",

year = "2004",

doi = "10.1007/978-3-540-25960-2_15",

language = "English",

isbn = "3-540-22113-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "19--52",

editor = "George Nemhauser and Daniel Bienstock",

booktitle = "Integer Programming and Combinatorial Optimization",

}

RIS

TY - CHAP

T1 - A faster exact separation algorithm for blossom inequalities

AU - Letchford, A N

AU - Reinelt, G

AU - Theis, D O

N1 - The full version of this paper appeared as: A.N. Letchford, G. Reinelt & D.O. Theis (2008) Odd minimum cut-sets and b-matchings revisited. SIAM J. Discr. Math., 22(4), 1480-1487.

PY - 2004

Y1 - 2004

N2 - In 1982, Padberg and Rao gave a polynomial-time separation algorithm for b-matching polyhedra. The current best known implementations of their separation algorithm run in O(|V|^2|E| log(|V|^2/|E|)) time when there are no edge capacities, but in O(|V||E|^2 log(|V|^2/|E|)) time when capacities are present. We propose a new exact separation algorithm for the capacitated case which has the same running time as for the uncapacitated case. For the sake of brevity, however, we will restrict our introduction to the case of perfect 1-capacitated b-matchings, which includes, for example, the separation problem for perfect 2-matchings. As well as being faster than the Padberg-Rao approach, our new algorithm is simpler and easier to implement.

AB - In 1982, Padberg and Rao gave a polynomial-time separation algorithm for b-matching polyhedra. The current best known implementations of their separation algorithm run in O(|V|^2|E| log(|V|^2/|E|)) time when there are no edge capacities, but in O(|V||E|^2 log(|V|^2/|E|)) time when capacities are present. We propose a new exact separation algorithm for the capacitated case which has the same running time as for the uncapacitated case. For the sake of brevity, however, we will restrict our introduction to the case of perfect 1-capacitated b-matchings, which includes, for example, the separation problem for perfect 2-matchings. As well as being faster than the Padberg-Rao approach, our new algorithm is simpler and easier to implement.

U2 - 10.1007/978-3-540-25960-2_15

DO - 10.1007/978-3-540-25960-2_15

M3 - Chapter (peer-reviewed)

SN - 3-540-22113-1

T3 - Lecture Notes in Computer Science

SP - 19

EP - 52

BT - Integer Programming and Combinatorial Optimization

A2 - Nemhauser, George

A2 - Bienstock, Daniel

PB - Springer

CY - Berlin

T2 - 10th International IPCO Conference

Y2 - 7 June 2004 through 11 June 2004

ER -

Research

Links

Text available via DOI: