Facets of the axial three-index assignment polytope

T. Dokka; F.C.R. Spieksma

doi:10.1016/j.dam.2015.07.018

Facets of the axial three-index assignment polytope

T. Dokka, F.C.R. Spieksma

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

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 language	English
Pages (from-to)	86-104
Journal	Discrete Applied Mathematics
Volume	201
DOIs	https://doi.org/10.1016/j.dam.2015.07.018
Publication status	Published - 11 Mar 2016
Externally published	Yes

Keywords

Three-dimensional assignment
Polyhedral methods
Facets
Separation algorithm

Access to Document

10.1016/j.dam.2015.07.018

Cite this

@article{7b570237fdd64f2b93f6386a28319d44,

title = "Facets of the axial three-index assignment polytope",

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

keywords = "Three-dimensional assignment, Polyhedral methods, Facets, Separation algorithm",

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

year = "2016",

month = mar,

day = "11",

doi = "10.1016/j.dam.2015.07.018",

language = "English",

volume = "201",

pages = "86--104",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Facets of the axial three-index assignment polytope

AU - Dokka, T.

AU - Spieksma, F.C.R.

PY - 2016/3/11

Y1 - 2016/3/11

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

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

KW - Three-dimensional assignment

KW - Polyhedral methods

KW - Facets

KW - Separation algorithm

U2 - 10.1016/j.dam.2015.07.018

DO - 10.1016/j.dam.2015.07.018

M3 - Article

SN - 0166-218X

VL - 201

SP - 86

EP - 104

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Facets of the axial three-index assignment polytope

Abstract

Keywords

Access to Document

Fingerprint

Cite this