Optimisation 2021/22

Master's degree in Modelling for Science and Engineering

C learning

Combinatorial Algorithms for graphs

  • General Bibliography
  • Additional information and tools
  • Compulsory Assignment

    A* Algorithm:
    Routing problem: Barcelona-Sevilla; the data map of spain can be downloaded from here (348.5Mb).
    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.
    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).
    To develop the program you can use the even much smaller data SabadellNodes.csv and SabadellStreets.csv (the files's format is specified inside the files in a comment line). The disadvantage in using this data is that the reading part of the program is different from the one needed to deal with the assignment.

    Optional Assignment

    Dijkstra Algorithm:
    Solve and implement the solution of the example Flight Agenda in the document Dijkstra's Application.
    As data you can use the following two files (if you have already done the assignment with some other data, please do not continue reading):
    As assignment you can find the flight agenda for the following itineraries (all of them with departure at 9am):

    Heuristics and problem representation

    Overview of optimization algorithms: Deterministic and heuristic

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

    Compulsory Assignment

    Solve the following Rosenbrock’s function exercise.

    Genetic Algorithms

    Optional Assignment (to train the skills in a canonical-academic problem)

    Maximization of a (complicate and artificial) function by a genetic algorithm.

    Compulsory Assignment

    A possible migration model.

    Simulated Annealing

    Optional Assignment

    Write a program that solves the N Queens Problem by means of a simulated annealing algorithm for N ≥ 8.
    The N Queens Problem consists in placing N queens in an N x N chess board so that no queen is threatening any other queen (queens threaten any queen in the same row, column or diagonal).

    Ant colony algorithms

    Optional Assignment

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

    Evaluation

    The list of assignments that will be proposed is the following:
    Assignment Status Deadline Maximum mark
    (pass is more than 49 points)
    Map routing (A* algorithm) Compulsory December 12, 2021 50 points
    Genetic Algorithm Compulsory January 9, 2022 30 points
    Deterministic Optimisation Compulsory February 6, 2022 20 points
    Dijkstra Algorithm Optional February 6, 2022 Together increment the final mark up to 20 points
    Simulated Annealing
    Ant Colony Algorithm