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)

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 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
PublisherSpringer
Chapter18
Pages189-200
Number of pages12
ISBN (Electronic)978-3-642-32147-4
ISBN (Print)978-3-642-32146-7
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event2nd International Symposium on Combinatorial Optimization (ISCO 2012) - Athens, Greece
Duration: 19 Apr 201221 Apr 2012
Conference number: 2
http://www.lamsade.dauphine.fr/~isco/ISCO2012/

Publication series

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

Conference

Conference2nd International Symposium on Combinatorial Optimization (ISCO 2012)
Abbreviated titleISCO 2012
CountryGreece
CityAthens
Period19/04/1221/04/12
Internet address

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

Cite this