Solving the Traveling Tournament Problem with Predefined Venues by Parallel Constraint Programming

被引：1

作者：

Liu, Ke ^{[1
]}

Loeffler, Sven ^{[1
]}

Hofstedt, Petra ^{[1
]}

机构：

[1] Brandenburg Univ Technol Cottbus Senftenberg, Dept Math & Comp Sci, Konrad Wachsmann Allee 5, D-03044 Cottbus, Germany

来源：

MINING INTELLIGENCE AND KNOWLEDGE EXPLORATION, MIKE 2018 | 2018年 / 11308卷

关键词：

Sports scheduling; Constraint programming; Parallel constraint solving; TTPPV;

D O I：

10.1007/978-3-030-05918-7_7

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The Traveling Tournament Problem with Predefined Venues (TTPPV) is a practical problem arising from sports scheduling. We describe two different modeling approaches for this problem, each of which is suitable for different sizes of instance. The experimental results show that our modeling approaches lead to improved performance compared to previous techniques in terms of the number of feasible solutions and the optimal value. Furthermore, we present how to execute the models in parallel through data-level parallelism. The parallel versions do not only gain speedup but also attain significant improvement on optimal value since more subtrees are searched independently.

引用

页码：64 / 79

页数：16

共 12 条

[1] Scheduling in sports: An annotated bibliography [J].

Kendall, Graham ;

Knust, Sigrid ;

Ribeiro, Celso C. ;

Urrutia, Sebastian .

COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (01) :1-19

[2] STR2: optimized simple tabular reduction for table constraints [J].

Lecoutre, Christophe .

CONSTRAINTS, 2011, 16 (04) :341-371

[3]

Lecoutre Christophe, 2009, Constraint Networks: Techniques and Algorithms

[4] The traveling tournament problem with predefined venues [J].

Melo, Rafael A. ;

Urrutia, Sebastian ;

Ribeiro, Celso C. .

JOURNAL OF SCHEDULING, 2009, 12 (06) :607-622

[5]

Pesant G., 2012, PRACTICE THEORY AUTO, P303

[6]

Pesant G., CSPLIB PROBLEM LIB C

[7]

Prud'homme C., 2017, TASC - LS2N CNRS UMR 6241

[8]

Régin JC, 2013, LECT NOTES COMPUT SC, V8124, P596, DOI 10.1007/978-3-642-40627-0_45

[9]

Rossi F, 2006, FOUND ARTIF INTELL, P1

[10]

Smith BM, 2006, FOUND ARTIF INTELL, P377

← 1 2 →