Optimisation

Master's degree in Modelling for Science and Engineering

C learning

Combinatorial Algorithms for graphs

  • General Bibliography
  • Compulsory Assignment

    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.

    Optional Assignment

    Dijkstra Algorithm:
    Solve exercises 12, 13 and 14 of the document Shortest path algorithms by Jeff Erickson, linked above.

    Heuristics and problem representation

    Overview of optimization algorithms: Deterministic and heuristic

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

    Compulsory Assignment

    Genetic Algorithms

    Compulsory Assignment for Optimisation

    Simulated Annealing

    Optional Assignment

    Ant colony algorithms

    Optional Assignment

    Crash mini-course on Machine Learning with Neural Networks

    Optional Assignment


    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 7/01/2020 50%
    Genetic Algorithm for Optimisation Compulsory 7/01/2020 30%
    Deterministic Optimisation Compulsory 9/02/2020 20%
    Dijkstra Algorithm Optional 9/02/2020 Together increment the final mark up to 20%
    Simulated Annealing
    Ant Colony Algorithm
    Neural Networks - Machine Learning