Design and analysis of computationally difficult instances is one of the promising areas in combinatorial optimization. The difficult benchmarks allow us to understand advantages and disadvantages of mathematical methods and incite new research directions. In this talk we present several new classes of benchmarks for the Uncapacitated Facility Location Problem. The first class is polynomially solvable. Nevertheless, it has many strong local optima and large mutual distance for each pair of them. Two other classes have exponential number of strong local optima. Finally, three last classes have large duality gap and one of them is the most difficult for the metaheuristics and the branch and bound method.
Groupe d’études et de recherche en analyse des décisions