Heavy tails in CP: The magic of restarts

One of the theoretical work with a great impact in practice on CP solving is the one on heavy tails phenomena:

Gomes, Carla P., Bart Selman, and Henry Kautz. "Boosting combinatorial search through randomization." Proceedings of AAAI,1998.

In essence this work says:

“There is a non negligible probability of hitting a problem that required exponentially more time to solve than any that had been encountered before”.

I ran some experiments with OscaR on the Sport Scheduling problem used in the paper:

• N (even) teams
• Every two teams plays each other exactly once
• The season last N-1 weeks
• Every team plays one game in each week of the season
• There are N/2 periods and, each week, every period is scheduled for one game
• No team plays more than twice in the same period over the course of the season

Here is a solution for 12 teams (N=12):

	week1	week2	week3	week4	week5	week6	week7	week8	week9	week10	week11
period1	(5,7)	(3,7)	(0,10)	(2,8)	(1,4)	(5,9)	(2,9)	(8,11)	(1,6)	(0,6)	(3,4)
period2	(3,11)	(5,8)	(4,7)	(6,7)	(0,2)	(3,10)	(1,8)	(4,10)	(5,11)	(1,9)	(2,6)
period3	(1,2)	(4,6)	(5,6)	(3,9)	(8,10)	(0,4)	(0,11)	(2,5)	(9,10)	(7,11)	(7,8)
period4	(4,9)	(2,10)	(8,9)	(1,10)	(6,11)	(2,11)	(4,5)	(0,7)	(0,3)	(3,8)	(1,5)
period5	(0,8)	(0,1)	(2,3)	(4,11)	(7,9)	(1,7)	(3,6)	(6,9)	(4,8)	(5,10)	(10,11)
period6	(6,10)	(9,11)	(1,11)	(0,5)	(3,5)	(6,8)	(7,10)	(1,3)	(2,7)	(2,4)	(0,9)

To solve this problem I use a first fail heuristic for the variable choice (the uninstanciated one with smallest domain size) with ties broken randomly. I choose randomly the value to instantiate.

Here is the OscaR model:

    val n = 12
    val nbPeriods = n / 2
    val Periods = 0 until nbPeriods
    val nbTeams = n
    val Teams = 0 until nbTeams
    val nbWeeks = n - 1
    val Weeks = 0 until nbWeeks
    val Homes = 0 to 1 // 0/1 for home/away game

    val cp = CPSolver()

    val team = Array.tabulate(nbPeriods, nbWeeks, 2)((p, w, h) => CPVarInt(cp, 0 until nbTeams))
    val game = Array.tabulate(nbPeriods, nbWeeks)((p, w) => CPVarInt(cp, 0 until (n * n - 1)))
    val tuples = for (i <- Teams; j <- i + 1 until nbTeams) yield (i, j, i * nbWeeks + j - 1)
    var solFound = false // will be set to true when a solution is found
    cp.solve subjectTo {
      // make the link between the team and game variables
      for (p <- Periods; w <- Weeks) {
        cp.add(table(team(p)(w)(0), team(p)(w)(1), game(p)(w), tuples))
      }
      // a team plays exactly one game per week
      for (w <- Weeks) {
        val teamw = for (p <- Periods; h <- Homes) yield team(p)(w)(h)
        cp.add(allDifferent(teamw), Strong)
      }
      // every team plays against every other team
      cp.add(allDifferent(game.flatten), Strong)
      // a team can play at most twice in the same period
      for (p <- Periods)
        cp.add(gcc(team(p).flatten, Teams, 1, 2), Strong)
    } exploration {
      cp.binary(game.flatten,_.size, _.randomValue) // our randomized heuristic
      solFound = true
    }
    cp.run(1) // let's start looking for a solution

I executed 10 runs stopping when the solution was found:

time(s)	bkts
82	117903
41	41548
900	900369
2	3634
6	8606
1	1749
6	9023
3	4291
674	1076619
1	577

As you can see, 2 runs took significantly more time than the others.

To avoid this problem Gomes et. al suggest to cuttoff the search (with a carefully chosen limit) and restart the search from scratch (don’t forget that the search is randomized so each run is different) until the solution is found.
From previous experiences I concluded that it is reasonable to think there is a quite high chance to solve this problem within 5000 backtrack limit. Here is the modified OscaR code to start the search making restarts until a solution is found (this replaces the previous call to run(1))

var restart = 0
do {
   cp.run(1, 5000) // search 1 sol with 5000 backtrack limit
   restart += 1
} while (!solFound)
println("#restart:" + restart)

Here is the result also giving the number of restarts before reaching a solution:

time(s)	#restarts
9	3
1	1
4	2
1	1
1	1
1	1
1	1
11	4
1	1
14	5

Looks like our few very long runs to find a solution have disappeared.  Much more robust, don’t you think? This is the magic of restarts, simple but powerful!