# The balanced $k-$ partitioning problem : how to design testbeds to compare different metaheuristics methods

I implemented different search metaheuristics methods (local search, Tabu search, and simulated annealing) on the problem of partitioning a non-oriented weighted graph' vertices into k parts of nearly equal size. I want to compare the methods. In the following article the author claim that :

• We can compare the deviation of the solution given by each method from the optimal solution but it's difficult to determine the optimal solution for large instances. One idea is to use geometrically constructed solutions for which optimal or near-optimal solutions are easy to determine despite the size of the instance. How to apply this idea on the k− balanced partitioning problem ?

• Classifying the problem instances being tested is critical to the proper analysis of heuristics. Differentiating factors between problem instances should be noted prior to any experimentation, and heuristic performance on each type of problem instance should be discussed. What are some of the important factors to classify the instances ?

Any help will be appreciated!