Consider the Graph Equipartition Problem: split the graph into two parts of almost the same size with the smallest number of edges between the two parts. Solve it using a greedy method, and then solve it using the simulated annealing heuristic. Compare your solutions. Experiment with various neighbourhoods and temperatures, dense graphs, sparse graphs, random graphs. Some comments:
- See section 12.3.2 and example 2.7 from the book [1].
- For details on simulated annealing, see Wikipedia, the survey [2], and the book [3]. For advanced study, an interested reader can read more in [4,5,6].
[1] L. A. Wolsey, Integer Programming, Wiley Interscience.
[2] C. Blum, A. Roli, Metaheuristics in Combinatorial Optimization: Overview and Conceptual
Comparison, online.
[3] S. Luke, Essentials of Metaheuristics: a set of undergraduate lecture notes, online.
[4] S. Clinton, Genetic algorithms with Python.
[5] K.-L. Du, M. N. S. Swamy, Search and optimization by metaheuristics: techniques and algorithms
inspired by nature.
[6] El G. Talbi, Metaheuristics: from design to implementation.