Facets of the axial three-index assignment polytope

T. Dokka, F.C.R. Spieksma

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We revisit the facial structure of the axial 3-index assignment polytope. After reviewing known classes of facet-defining inequalities, we present a new class of valid inequalities, and show that they define facets of this polytope. This answers a question posed by Qi and Sun (2000). Moreover, we show that we can separate these inequalities in polynomial time. Finally, we assess the computational relevance of the new inequalities by performing (limited) computational experiments.
Original languageEnglish
Pages (from-to)86-104
JournalDiscrete Applied Mathematics
Volume201
DOIs
Publication statusPublished - 11 Mar 2016
Externally publishedYes

Keywords

  • Three-dimensional assignment
  • Polyhedral methods
  • Facets
  • Separation algorithm

Cite this