Optimisation (2014/15)

Master's degree in Modelling for Science and Engineering

C learning

Combinatorial Algorithms for graphs


Dijkstra Algorithm (recommended):
Solve the project proposed here.
A* Algorithm (compulsory):
Routing problem: Barcelona-Sevilla; the data map of spain can be downloaded from here (348.5Mb).
For testing the program, you can use the much smaller file catalunya.csv.zip (51.9Mb) (it has only 3472620 nodes and 201235 ways and it has the same format as the file spain.csv.zip). Valid nodes ID for start and goal are: 771979683 (in Girona) and 429854583 (in Lleida).

Genetic Algorithms


First exercise (compulsory part): Vertex coloring of graphs.
Second exercise (optional part): Maximization of a (complicate and artificial) function by a genetic algorithm

Simulated Annealing


In the N Queens puzzle you have an N x N chess board.
On it you must place N queens so that no queen is threatening any other queen.
Queens threaten any queen in the same row, column or diagonal.

Write a program that solves the N queens problem by using simulated annealing.

Ant colony algorithms


A traveling salesman must visit all cities appearing in the table of distances between European cities starting and ending in Barcelona. He travels by car. Solve this traveling salesman problem by using an Ant Colony System. Take edge probabilities of the form stated in page 249 of the [Dorigo, Blum] paper.



The list of assignments that will be proposed is the following:
Assignment Status  Deadline  Weight in the final mark
Dijkstra Algorithm Recommended November 16, 2014 5%
Map routing (A* algorithm) Compulsory January 11, 2015 60% (50%)
Genetic Algorithm Compulsory January 31st, 2015 40% (35%)
Genetic Algorithm (2nd) Optional February 28, 2015 Together increment the final mark up to 20%
Simulated Annealing
Ant Colony Algorithm Recommended February 28, 2015 10%