Fast separation algorithms for three-index assignment problems

T. Dokka; I. Mourtos; F.C.R. Spieksma

doi:10.1007/978-3-642-32147-4_18

Fast separation algorithms for three-index assignment problems

T. Dokka, I. Mourtos, F.C.R. Spieksma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

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 '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).

Original language	English
Title of host publication	Combinatorial Optimization
Subtitle of host publication	Second International Symposium, ISCO 2012, Revised Selected Papers
Editors	A.R. Mahjoub, V. Markakis, I. Milis, V.T. Paschos
Place of Publication	Berlin
Publisher	Springer
Chapter	18
Pages	189-200
Number of pages	12
ISBN (Electronic)	978-3-642-32147-4
ISBN (Print)	978-3-642-32146-7
DOIs	https://doi.org/10.1007/978-3-642-32147-4_18
Publication status	Published - 2012
Externally published	Yes
Event	2nd International Symposium on Combinatorial Optimization (ISCO 2012) - Athens, Greece Duration: 19 Apr 2012 → 21 Apr 2012 Conference number: 2 http://www.lamsade.dauphine.fr/~isco/ISCO2012/

Publication series

Name	Lecture Notes in Computer Science
Volume	7422
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd International Symposium on Combinatorial Optimization (ISCO 2012)
Abbreviated title	ISCO 2012
Country	Greece
City	Athens
Period	19/04/12 → 21/04/12
Internet address	http://www.lamsade.dauphine.fr/~isco/ISCO2012/

Access to Document

10.1007/978-3-642-32147-4_18

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Fast separation algorithms for three-index assignment problems'. Together they form a unique fingerprint.

Cite this

Dokka, T., Mourtos, I., & Spieksma, F. C. R. (2012). Fast separation algorithms for three-index assignment problems. In A. R. Mahjoub, V. Markakis, I. Milis, & V. T. Paschos (Eds.), Combinatorial Optimization : Second International Symposium, ISCO 2012, Revised Selected Papers (pp. 189-200). (Lecture Notes in Computer Science ; Vol. 7422). Springer. https://doi.org/10.1007/978-3-642-32147-4_18

@inproceedings{6f20d4fe3f664d2db4c75dcdf0442550,

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 '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).",

author = "T. Dokka and I. Mourtos and F.C.R. Spieksma",

year = "2012",

doi = "10.1007/978-3-642-32147-4_18",

language = "English",

isbn = "978-3-642-32146-7",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "189--200",

editor = "A.R. Mahjoub and V. Markakis and I. Milis and V.T. Paschos",

booktitle = "Combinatorial Optimization",

address = "Germany",

note = "2nd International Symposium on Combinatorial Optimization (ISCO 2012), ISCO 2012 ; Conference date: 19-04-2012 Through 21-04-2012",

url = "http://www.lamsade.dauphine.fr/~isco/ISCO2012/",

}

Dokka, T, Mourtos, I & Spieksma, FCR 2012, Fast separation algorithms for three-index assignment problems. in AR Mahjoub, V Markakis, I Milis & VT Paschos (eds), Combinatorial Optimization : Second International Symposium, ISCO 2012, Revised Selected Papers. Lecture Notes in Computer Science , vol. 7422, Springer, Berlin, pp. 189-200, 2nd International Symposium on Combinatorial Optimization (ISCO 2012), Athens, Greece, 19/04/12. https://doi.org/10.1007/978-3-642-32147-4_18

Fast separation algorithms for three-index assignment problems. / Dokka, T.; Mourtos, I.; Spieksma, F.C.R.

Combinatorial Optimization : Second International Symposium, ISCO 2012, Revised Selected Papers. ed. / A.R. Mahjoub; V. Markakis; I. Milis; V.T. Paschos. Berlin : Springer, 2012. p. 189-200 (Lecture Notes in Computer Science ; Vol. 7422).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Fast separation algorithms for three-index assignment problems

AU - Dokka, T.

AU - Mourtos, I.

AU - Spieksma, F.C.R.

N1 - Conference code: 2

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).

UR - http://www.scopus.com/inward/record.url?scp=84865235081&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-32147-4_18

DO - 10.1007/978-3-642-32147-4_18

M3 - Conference contribution

AN - SCOPUS:84865235081

SN - 978-3-642-32146-7

T3 - Lecture Notes in Computer Science

SP - 189

EP - 200

BT - Combinatorial Optimization

A2 - Mahjoub, A.R.

A2 - Markakis, V.

A2 - Milis, I.

A2 - Paschos, V.T.

PB - Springer

CY - Berlin

T2 - 2nd International Symposium on Combinatorial Optimization (ISCO 2012)

Y2 - 19 April 2012 through 21 April 2012

ER -

Dokka T, Mourtos I, Spieksma FCR. Fast separation algorithms for three-index assignment problems. In Mahjoub AR, Markakis V, Milis I, Paschos VT, editors, Combinatorial Optimization : Second International Symposium, ISCO 2012, Revised Selected Papers. Berlin: Springer. 2012. p. 189-200. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-642-32147-4_18