A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem

Marije R. Siemann; Matthias Walter

doi:10.1016/j.disopt.2022.100741

A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem

Marije R. Siemann^*, Matthias Walter

^*Corresponding author for this work

Mathematics of Operations Research

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

8 Downloads (Pure)

Abstract

We consider the unconstrained traveling tournament problem, a sports timetabling problem that minimizes traveling of teams. Since its introduction about 20 years ago, most research was devoted to modeling and reformulation approaches. In this paper we carry out a polyhedral study for the cubic integer programming formulation by establishing the dimension of the integer hull as well as of faces induced by model inequalities. Moreover, we introduce a new class of inequalities and show that they are facet-defining. Finally, we evaluate the impact of these inequalities on the linear programming bounds.

Original language	English
Article number	100741
Number of pages	33
Journal	Discrete optimization
Volume	46
DOIs	https://doi.org/10.1016/j.disopt.2022.100741
Publication status	Published - Nov 2022

Access to Document

10.1016/j.disopt.2022.100741Licence: CC BY

A polyhedral studyFinal published version, 897 KBLicence: CC BY

1 Working paper

A Polyhedral Study for the Cubic Formulation of the Unconstrained Traveling Tournament Problem
Siemann, M. & Walter, M., 18 Nov 2020, ArXiv.org, 29 p.
Research output: Working paper

Open Access
File

Cite this

@article{f29775738722432e9d639c5310ccb13d,

title = "A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem",

abstract = "We consider the unconstrained traveling tournament problem, a sports timetabling problem that minimizes traveling of teams. Since its introduction about 20 years ago, most research was devoted to modeling and reformulation approaches. In this paper we carry out a polyhedral study for the cubic integer programming formulation by establishing the dimension of the integer hull as well as of faces induced by model inequalities. Moreover, we introduce a new class of inequalities and show that they are facet-defining. Finally, we evaluate the impact of these inequalities on the linear programming bounds.",

author = "Siemann, {Marije R.} and Matthias Walter",

year = "2022",

month = nov,

doi = "10.1016/j.disopt.2022.100741",

language = "English",

volume = "46",

journal = "Discrete optimization",

issn = "1572-5286",

publisher = "Elsevier",

}

TY - JOUR

T1 - A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem

AU - Siemann, Marije R.

AU - Walter, Matthias

PY - 2022/11

Y1 - 2022/11

N2 - We consider the unconstrained traveling tournament problem, a sports timetabling problem that minimizes traveling of teams. Since its introduction about 20 years ago, most research was devoted to modeling and reformulation approaches. In this paper we carry out a polyhedral study for the cubic integer programming formulation by establishing the dimension of the integer hull as well as of faces induced by model inequalities. Moreover, we introduce a new class of inequalities and show that they are facet-defining. Finally, we evaluate the impact of these inequalities on the linear programming bounds.

AB - We consider the unconstrained traveling tournament problem, a sports timetabling problem that minimizes traveling of teams. Since its introduction about 20 years ago, most research was devoted to modeling and reformulation approaches. In this paper we carry out a polyhedral study for the cubic integer programming formulation by establishing the dimension of the integer hull as well as of faces induced by model inequalities. Moreover, we introduce a new class of inequalities and show that they are facet-defining. Finally, we evaluate the impact of these inequalities on the linear programming bounds.

U2 - 10.1016/j.disopt.2022.100741

DO - 10.1016/j.disopt.2022.100741

M3 - Article

VL - 46

JO - Discrete optimization

JF - Discrete optimization

SN - 1572-5286

M1 - 100741

ER -

A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem

Abstract

Access to Document

Fingerprint

Research output

A Polyhedral Study for the Cubic Formulation of the Unconstrained Traveling Tournament Problem

Cite this