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.
翻译：我们认为不受限制的旅行锦标赛问题是一个体育计时问题,它尽量减少了团队的差旅。自大约20年前开始以来,大多数研究都专注于模型和重新制定方法。在这份文件中,我们通过确定整体尺寸和模型不平等所诱发的面孔,对立方整数方案拟订进行了多面研究。此外,我们引入了新的不平等类别,并表明它们具有面性。最后,我们评估了这些不平等对线性编程界限的影响。
相关内容
微信扫码咨询专知VIP会员