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

Marije Siemann, Matthias Walter

Research output: Working paperProfessional

69 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 languageEnglish
PublisherArXiv.org
Number of pages29
Publication statusPublished - 18 Nov 2020

Keywords

  • cs.DM
  • math.OC
  • 90C57
  • G.2.0

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