Applications and examples

Applications

• Applications and examples:

• Assigning frequencies in mobile networks
• Scheduling problems
• Timetabling
• Register allocation in compilers
• Four color theorem
• Sudoku

Basic Representation for K-coloring

• Configuration C = a vector of labels/colors

• The conflict number of C:

• The number of edges with both ends of the same color

• K-coloring problem ≈ find configuration C* minimizing the conflict number

• The problem is solved if C* has no conflicts

The Landscape for K-colouring

• The set of all possible configurations has cardinal K|V| ~ a space of dimension |V|

• The neighbourhood relation:

• We pass from a
• configuration C to C’
• by changing just one
• colour in a conflicting
• vertex of C

Related Works

• Exact algorithms: |V| <100

• Inexact algorithms

• Metaheuristics (working on landscape):
• Local Search: Tabu Search, Simulated Annealing [Hertz et Al, A variable neighborhood search for graph coloring, 2003], [Zufferey et. al, A graph coloring heuristic using partial solutions and a reactive tabu scheme, 2007]
• Evolutionary algorithms [Fleurent et. Al, Genetic and hybrid algorithms for graph coloring, 1996], [Hao et Al, Hybrid Evolutionary Algorithms for Graph Coloring, 1999][Galinier et Al, An adaptive memory algorithm for graph coloring,2004]
• Sequential construction: DSatur Algorithm, RLS

Steepest Descent

• It starts from a random configuration

• At each step, we move to the best neighbouring configuration
• We stop when it is no longer possible to find better neighbouring configurations (in a local minimum)

Steepest Descent: Cases

Tabu Search

• A steepest descent that can perform “up moves”

• We can move to a worse configuration when there is no possible move not increasing the number of conflicts

• Risk : to repeat a set of moves again and again

• => Tabu list = a list of temporary forbidden moves

Tabu Search: evolution of the number of conflicts

Tabu Search: evolution of the number of conflicts

Tabu Search: evolution of the number of conflicts

Tabu List Length

• The role of the tabu list is to restrain the algorithm from cycling in a local plateau

• Tabu List Length: tl = RandomInt(0,10) + f
• Each time we perform move m, we forbid the algorithm from re-applying m on next tl moves

•  tl = 2  enough to break a cycle of length 2

Tabu List Length

• The same tabu list length = 2 is NOT enough to break larger cycles

• We can find both very small or very large plateaus small or large cycles

• Long tabu list for large plateaus and small tabu list for small plateaus

Adaptive Tabu List Length

• We double the tabu list length when we stayed X moves at the same conflict number

• A constant very long tabu list length would forbid a move (an assignment of a color) for much too long!

New Evaluation Function

• In most algorithms, all configurations are compared and assessed with the classical evaluation function f

• Not all conflicts are as difficult to solve

• We can have:

• Edges with easy conflicts (V3-V4)
• We can simply change the color in one end
• Edges with hard conflicts (V3-V2)
• We cannot change a color without generating new conflicts

Degree-based Evaluation

• {i,j} Easy conflict in C1{i,k} Hard conflict in C2

• Vertex j: degree=1   Vertex k: degree=6

• 

• Each edge has a weight, according to the degree of each vertex

RTS vs. Other Tabu Algorithms

• RTS gains one colour on 75% of the Dimacs graphs - in comparison with the same algorithm without the two improvements

• RTS gains one colour in 50% of graphs in comparison with the best of all Tabu algorithms ever written

• The new evaluation function gains one colour in 25% of cases vs classical evaluation function

RTS vs Best Algorithms

• The best algorithms are often population-based hybrid algorithms

• RTS is able to find the best colorings ever reported for 75% of the Dimacs graphs (28 out of the 38)

• We obtained the best results of previous local search algorithms in almost 100% of cases (2 exceptions)

Conclusions

• Two simple techniques are enough to make a basic local search provide very competitive results.

• Tabu Search can now attain the best results ever found in 75% of the Dimacs graphs