Optimisation 2017/18

Master's degree in Modelling for Science and Engineering

C learning

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

    Overview of optimization algorithms: Deterministic and heuristic

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

    Assignments

    Genetic Algorithms

    Assignments

    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.

    Ant colony algorithms

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

    Particle Swarm Optimisation

    Assignments

    Neural Networks and Machine Learning

    Taught by Josep Maria Lago

    Evaluation

    The list of assignments that will be proposed is the following:
    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