# Optimisation (2014/15)

## Combinatorial Algorithms for graphs

### Assignments:

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

### Assignments:

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

### Assignments:

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

### Assignments

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.

## Evaluation

 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%

• For each assignment a report must be written including:
• introduction stating the problem and the algorithm to solve it,
• the code of the program,
• the results of running the program and
• conclusions.
• The quality of the code of the program will be taken into account for the marks of the assignments and discussed in the interviews.