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

Marije Siemann; Matthias Walter

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

Marije Siemann, Matthias Walter

Mathematics of Operations Research

Research output: Working paper

5 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
Publisher	arXiv.org
Number of pages	29
Publication status	Published - 18 Nov 2020

Keywords

cs.DM
math.OC
90C57
G.2.0

Access to Document

2011.09135v1Final published version, 382 KB

Fingerprint Dive into the research topics of 'A Polyhedral Study for the Cubic Formulation of the Unconstrained Traveling Tournament Problem'. Together they form a unique fingerprint.

Cite this

@techreport{08e67c799afa4d35bb954b9b5aa3bcc3,

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

keywords = "cs.DM, math.OC, 90C57, G.2.0",

author = "Marije Siemann and Matthias Walter",

year = "2020",

month = nov,

day = "18",

language = "English",

publisher = "arXiv.org",

type = "WorkingPaper",

institution = "arXiv.org",

}

TY - UNPB

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

AU - Siemann, Marije

AU - Walter, Matthias

PY - 2020/11/18

Y1 - 2020/11/18

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.

KW - cs.DM

KW - math.OC

KW - 90C57

KW - G.2.0

M3 - Working paper

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

PB - arXiv.org

ER -