Challenge Traveling Tournament Instances (Relaxed)

Last Update: May 10, 2013

Description of the Problem

This problem is a variant of the Traveling Tournament Problem and is proposed by Renjun Bao and Michael Trick. In this variant, the schedule is not compact: teams have byes in their schedule. The number of byes is controlled by a parameter K, the number of byes per team in the schedule. K=0 corresponds to the normal TTP.

Byes are ignored in determining the length of a homestand or roadtrip, and in determining whether a repeater has occured.

Instances and Best Values

Any instance from the Traveling Tournament Problem can be used for this.

• NL4, K=1. UB: 8160 (Bao and Trick, August 9, 2010); LB: 8160 (Bao and Trick, August 9, 2010)
• NL4, K=2. UB: 8160 (Bao and Trick, August 9, 2010); LB: 8160 (Bao and Trick, August 9, 2010)
• NL4, K=3. UB: 8044 (Bao and Trick, August 9, 2010); LB: 8044 (Bao and Trick, August 9, 2010)
• super4 k=1 UB: 63334 (Brandão, November 15, 2012); LB: 63334 (Brandão, November 15, 2012)
• super4 k=2 UB: 63263 (Brandão, November 15, 2012); LB: 63263 (Brandão, November 15, 2012)
• super4 k>=3 UB: 63192 (Brandão, November 15, 2012); LB: 63192 (Brandão, November 15, 2012)
• galaxy4, k=1 UB: 414 (Brandão, November 15, 2012); LB: 414 (Brandão, November 15, 2012)
• galaxy4, k=2 UB: 413 (Brandão, November 15, 2012); LB: 413 (Brandão, November 15, 2012)
• galaxy4, k>=3 UB: 412 (Brandão, November 15, 2012); LB: 412 (Brandão, November 15, 2012)
• circ4, k=1 UB: 18 (Brandão, November 15, 2012); LB: 18 (Brandão, November 15, 2012)
• circ4, k=2 UB: 18 (Brandão, November 15, 2012); LB: 18 (Brandão, November 15, 2012)
• circ4, k>=32 UB: 16 (Brandão, November 15, 2012); LB: 16 (Brandão, November 15, 2012)
• CON4, K>=1. UB/LB: 16 (Brandão, January 5, 2013)
• CON6, K=1. UB: 42 (Bao and Trick, August 9, 2010); LB: 42 (Bao and Trick, August 9, 2010)
• CON6, K>=1, UB/LB: 42 (Brandão, January 5, 2013)
• NL6, K=1. UB: 23791 (Bao and Trick, August 9, 2010), 23188 (Brandão, October 4 2010), 23124 (Brandão, October 8 2010); LB: 22642 (Bao and Trick, August 9, 2010)
• NL6, K>=2. UB: 22557 (Brandão, October 8 2010); LB: 22557 (Brandão, October 8 2010)
• super6 k=1 UB: 127903 (Brandão, November 15, 2012); LB: 127903 (Brandão, November 15, 2012)
• super6 k>=2 UB: 127370 (Brandão, November 15, 2012); LB: 127370 (Brandão, November 15, 2012)
• galaxy6, k=1 UB: 1330 (Brandão, November 15, 2012); LB: 1330 (Brandão, November 15, 2012)
• galaxy6, k>=2 UB: 1294 (Brandão, November 15, 2012); LB: 1294 (Brandão, November 15, 2012)
• circ6, k>=1 UB: 60 (Brandão, November 15, 2012); LB: 60 (Brandão, November 15, 2012)
• NL8, K=1. UB: 39128 (Brandão, October 27 2010); LB: 39128 (Brandão, October 17 2010)
• NL8, K=2. UB: 38761 (Brandão, October 27 2010); LB: 38761 (Brandão, October 17 2010)
• NL8, K>=3. UB: 38670 (Brandão, October 27 2010); LB: 38670 (Brandão, October 17 2010)
• CON8, K>=0, UB/LB: 80 (Brandão, January 5, 2013)
• super8, K=1, UB/LB: 178115 (Brandão, January 5, 2013)
• super8, k=2, UB/LB: 177406 (Brandão, January 5, 2013)
• super8, K>=3, UB/LB: 177258 (Brandão, January 5, 2013)
• galaxy8, K=1, UB/LB: 2298 (Brandão, January 5, 2013)
• galaxy8, K=2, UB/LB: 2261 (Brandão, January 5, 2013)
• galaxy8, K>=3, UB/LB: 2250 (Brandão, January 5, 2013)
• NL10, K=1. UB: 59425 (Perez and Riff, August 6, 2011);
• NL10, K=2. UB: 59373 (Perez and Riff, August 6, 2011);