In this homework you will solve
- Sorting optimization problem, and
- Minimum spanning tree (MST) problem
using
- Simulated Annealing, and - Variable Neighborhood Search.
1. Design and implement Simulated Annealing based algorithm for both problems (MST and sorting optimization problem).
2. Design and implement Variable Neighborhood Search based algorithm for both problems (MST and sorting optimization problem).
3. Write a report about your work. In your report, you should
- give the rigorous and in detailed definition of the optimization problems that you used to design your algorithms.
- give explanation of your design. If there are alternatives for a design decision, explain why you choose the one in your design. Write pseudo-code of your algorithms.
- explain non-trivial implementation details in your code.
- present the theoretical run-time analysis
- present the results of experimental analysis. Run your algorithms for several benchmark problems (of various complexities and sizes) and present their performance. Draw figures and tables.
Note that you will work with the same (or very similar) problems for future homework assignments and design algorithms using following design techniques, as well.
- Tabu Search
- Genetic Algorithms
- Particle Swarm Optimization
- Ant Colony Optimization
