# Optimisation 2017/18

## Combinatorial Algorithms for graphs

• General Bibliography
• ### Assignments

Dijkstra Algorithm:
Solve exercises 12, 13 and 14 of the document Shortest path algorithms by Jeff Erickson, linked above.
A* Algorithm:
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).
Here you can find my solution of the Barcelona-Sevilla problem for reference (recall that it depends globally on the distance formula). in the setting of the memory structure recommended in the assignment.
Here you can find an example of writing/reading the graph to/from a binary file in the setting of the memory structure recommended in the assignment.

## Heuristics and problem representation

• Heuristics: Intelligent Search Strategies for Computer Problem Solving, Judea Pearl
Addison-Wesley Pub (Sd) | ISBN: 0201055945 | 1984-04 | djvu (ocr) | 399 pages | 3.66 Mb
Chapter 1; Pages 3-13 and 27-31.
• Hanoi Towers

## Deterministic optimization for nonlinear problems (constrained and non-constrained)

• Newton and Quasi-Newton methods
• Levenberg Marquardt
• Karush-Kuhn-Tucker conditions for constrained optimization
• Penalty and Barrier Methods for constrained optimization

## Simulated Annealing

### Assignments

We have to load a truck with some goods. The values and the weights of these goods are listed here, and the truck can carry a maximum weight of 600 Kg. We want to maximize the total value of the taken goods.

## Concrete Examples

### 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. Use an ACO to compute the optimum route according to driving distance (take edge probabilities of the form stated in page 249 of the [Dorigo, Blum] paper).

## Neural Networks and Machine Learning

Taught by Josep Maria Lago

## Evaluation

 Assignment Status Deadline Weight in the final mark Map routing (A* algorithm) Compulsory 10/02/2017 60% Genetic Algorithm Compulsory 10/02/2017 40% Dijkstra Algorithm Optional 10/02/2017 Together increment the final mark up to 20% Deterministic Optimisation Simulated Annealing Ant Colony Algorithm Machine Learning

• 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.