Standard
Fast Separation Algorithms for Three-Index Assignment Problems. /
Dokka, Trivikram; Mourtos, I; Spieksma, Frits C.r.
Combinatorial optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, revised selected papers. ed. / A. Ridha Mahjoub; Vangelis Markakis; Ioannis Milis; Vangelis Th. Paschos. New York: Springer Berlin Heidelberg, 2012. p. 189-200 (Lecture Notes in Computer Science; Vol. 7422).
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter
Harvard
Dokka, T, Mourtos, I & Spieksma, FCR 2012,
Fast Separation Algorithms for Three-Index Assignment Problems. in A Ridha Mahjoub, V Markakis, I Milis & VT Paschos (eds),
Combinatorial optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, revised selected papers. Lecture Notes in Computer Science, vol. 7422, Springer Berlin Heidelberg, New York, pp. 189-200.
https://doi.org/10.1007/978-3-642-32147-4_18
APA
Dokka, T., Mourtos, I., & Spieksma, F. C. R. (2012).
Fast Separation Algorithms for Three-Index Assignment Problems. In A. Ridha Mahjoub, V. Markakis, I. Milis, & V. T. Paschos (Eds.),
Combinatorial optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, revised selected papers (pp. 189-200). (Lecture Notes in Computer Science; Vol. 7422). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-32147-4_18
Vancouver
Dokka T, Mourtos I, Spieksma FCR.
Fast Separation Algorithms for Three-Index Assignment Problems. In Ridha Mahjoub A, Markakis V, Milis I, Paschos VT, editors, Combinatorial optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, revised selected papers. New York: Springer Berlin Heidelberg. 2012. p. 189-200. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-32147-4_18
Author
Dokka, Trivikram ; Mourtos, I ; Spieksma, Frits C.r. /
Fast Separation Algorithms for Three-Index Assignment Problems. Combinatorial optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, revised selected papers. editor / A. Ridha Mahjoub ; Vangelis Markakis ; Ioannis Milis ; Vangelis Th. Paschos. New York : Springer Berlin Heidelberg, 2012. pp. 189-200 (Lecture Notes in Computer Science).
Bibtex
@inbook{08205b0b5af94135bb9adc373b156b41,
title = "Fast Separation Algorithms for Three-Index Assignment Problems",
abstract = "In polyhedral combinatorics, the polytope related to a combinatorial optimization problem is examined in order to obtain families of valid inequalities. To incorporate such families of inequalities within a {\textquoteleft}Branch & Cut{\textquoteright} algorithm requires one further step: that of deriving an algorithm which determines whether an inequality of a specific family is violated by a given vector (the separation problem). The idea put forward in this work is to consider a compact representation of the given vector, and measure the complexity of a separation algorithm in terms of this compact representation. We illustrate the idea on the separation of known inequalities for the three index assignment polytope. It turns out that we find new separation algorithms with better complexities than the current ones (that were called best possible).",
author = "Trivikram Dokka and I Mourtos and Spieksma, {Frits C.r.}",
year = "2012",
doi = "10.1007/978-3-642-32147-4_18",
language = "English",
isbn = "9783642321467",
series = "Lecture Notes in Computer Science",
publisher = "Springer Berlin Heidelberg",
pages = "189--200",
editor = "{Ridha Mahjoub}, A. and Vangelis Markakis and Ioannis Milis and Paschos, {Vangelis Th.}",
booktitle = "Combinatorial optimization",
}
RIS
TY - CHAP
T1 - Fast Separation Algorithms for Three-Index Assignment Problems
AU - Dokka, Trivikram
AU - Mourtos, I
AU - Spieksma, Frits C.r.
PY - 2012
Y1 - 2012
N2 - In polyhedral combinatorics, the polytope related to a combinatorial optimization problem is examined in order to obtain families of valid inequalities. To incorporate such families of inequalities within a ‘Branch & Cut’ algorithm requires one further step: that of deriving an algorithm which determines whether an inequality of a specific family is violated by a given vector (the separation problem). The idea put forward in this work is to consider a compact representation of the given vector, and measure the complexity of a separation algorithm in terms of this compact representation. We illustrate the idea on the separation of known inequalities for the three index assignment polytope. It turns out that we find new separation algorithms with better complexities than the current ones (that were called best possible).
AB - In polyhedral combinatorics, the polytope related to a combinatorial optimization problem is examined in order to obtain families of valid inequalities. To incorporate such families of inequalities within a ‘Branch & Cut’ algorithm requires one further step: that of deriving an algorithm which determines whether an inequality of a specific family is violated by a given vector (the separation problem). The idea put forward in this work is to consider a compact representation of the given vector, and measure the complexity of a separation algorithm in terms of this compact representation. We illustrate the idea on the separation of known inequalities for the three index assignment polytope. It turns out that we find new separation algorithms with better complexities than the current ones (that were called best possible).
U2 - 10.1007/978-3-642-32147-4_18
DO - 10.1007/978-3-642-32147-4_18
M3 - Chapter
SN - 9783642321467
T3 - Lecture Notes in Computer Science
SP - 189
EP - 200
BT - Combinatorial optimization
A2 - Ridha Mahjoub, A.
A2 - Markakis, Vangelis
A2 - Milis, Ioannis
A2 - Paschos, Vangelis Th.
PB - Springer Berlin Heidelberg
CY - New York
ER -