Home > Research > Publications & Outputs > Fast Separation Algorithms for Three-Index Assi...
View graph of relations

Fast Separation Algorithms for Three-Index Assignment Problems

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNChapter

Published
Close
Publication date2012
Host publicationCombinatorial optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, revised selected papers
EditorsA. Ridha Mahjoub, Vangelis Markakis, Ioannis Milis, Vangelis Th. Paschos
Place of PublicationNew York
PublisherSpringer Berlin Heidelberg
Pages189-200
Number of pages12
ISBN (Print)9783642321467
<mark>Original language</mark>English

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7422
ISSN (Print)0302-9743

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