Fast separation algorithms for three-index assignment problems

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


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 languageEnglish
Title of host publicationCombinatorial Optimization
Subtitle of host publicationSecond International Symposium, ISCO 2012, Revised Selected Papers
EditorsA.R. Mahjoub, V. Markakis, I. Milis, V.T. Paschos
Place of PublicationBerlin
Number of pages12
ISBN (Electronic)978-3-642-32147-4
ISBN (Print)978-3-642-32146-7
Publication statusPublished - 2012
Externally publishedYes
Event2nd International Symposium on Combinatorial Optimization (ISCO 2012) - Athens, Greece
Duration: 19 Apr 201221 Apr 2012
Conference number: 2

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference2nd International Symposium on Combinatorial Optimization (ISCO 2012)
Abbreviated titleISCO 2012
Internet address


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

Cite this