Optimisation 2009—2021

C learning

Combinatorial Algorithms for graphs

• Graphs general definitions and graph traversal algorithms (in translation to english process) slides, and printable slides (2x2 pages per sheet).
• Shortest paths algorithms in weighted graphs: Dijstra and A* algorithms slides, and printable slides (2x2 pages per sheet).

• Graph Theory: Introduction
• Search in Graphs: Depth-first and Breadth-first.
• Greedy algorithm
• Dijkstra Algorithm by Eric Demaine (printable booklet version)
• Dijkstra Algorithm Notes (Notes of COMP271: Design and Analysis of Algorithms), Mordecai J.GOLIN
  Department of Computer Science & Engineering,
  Hong Kong University of Science & Technology.
• Dijkstra Animated: a simple example and an example with more nodes
• Best-first search
• Introduction to A* Algorithms
• 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
  Pages used: 33 to 46, 48, 49, 64, 65, 73--85. Also the example in pages 52--54 might be relevant.
• Shortest path algorithms by Jeff Erickson

• The promised code to read the file of Sabadell Streets

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

• Flight201301u.zip contains a flight time table taken from https://dataverse.harvard.edu/dataset.xhtml?persistentId=doi:10.7910/DVN/COHFWA but with serious modifications (which implies that the flights are no longer true). Among the simplifications, we assume that all flights operate every day. Each line contains:
  • Departure airport code;
  • Arrival airport code;
  • Departure time (in departure airport time zone);
  • Arrival time (in arrival airport time zone);
  • Number of days: 1 means that it arrives the day after, 2 means that it arrives two days after.
  • Elapsed time as HHHMM. For example 00150 means 1 hour, 50 minutes.
  
  Caution: This big list of flights contains more than one connected component: that is, not all possible trips can be done. For example:
  • MCG is an isolated point.
  • ZEL is just connected to YKT and vice-versa.
• Airports.zip contains information about the airports. In particular, from the airport code you can extract the city or name of the airport. The file is taken from: https://openflights.org/data.html

As assignment you can find the flight agenda for the following itineraries (all of them with departure at 9am):

• Itinerary 1:
  • Departure: REU, "Reus Air Base","Reus"
  • Arrival: ILD, "Lleida-Alguaire Airport","Lleida"
• Itinerary 2:
  • Departure: AAA, Anaa Airport in French Polynesia.
  • Arrival: GKA, Goroka Airport in Papua New Guinea.
• Itinerary 3:
  • Departure: GDT, "JAGS McCartney International Airport","Cockburn Town","Turks and Caicos Islands"
  • Arrival: JGO, "Qeqertarsuaq Heliport","Qeqertarsuaq Airport","Greenland"

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

Overview of optimization algorithms: Deterministic and heuristic

• Overview of heuristic optimization methods
• A simple function difficult to minimize

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

• Gradient descent ("steepest descent")
• Newton and Quasi-Newton methods
• Conjugate gradient methods
• Levenberg Marquardt
• Karush-Kuhn-Tucker conditions for constrained optimization
• Penalty and Barrier Methods for constrained optimization

• Basic bibliography
• Numerical Mathematics, Alfio Quarteroni, Riccardo Sacco, Fausto Saleri, Texts in Applied Mathematicsm 37, Springer, 1991.
• Gauss-Newton/Levenberg-Marquardt Optimization (Ethan Eade)
• Convex Optimization (Lieven Vandenberghe)
Optimization with inequality constraints: the Kuhn-Tucker conditions; a simple approach
• Kuhn–Tucker Conditions
• Karush-Kuhn-Tucker conditions (Geoff Gordon & Ryan Tibshirani)
• Penalty and Barrier Methods for constrained optimization
• Luenberger: Linear and Nonlinear Programming

Compulsory Assignment

Genetic Algorithms

• Basic bibliography
• Transparencies of Jacek Dziedzic (full version)
• Essentials of Metaheuristics, A Set of Undergraduate Lecture Notes, Sean Luke,
  Department of Computer Science, George Mason University.
• Additional bibliography
• An Overview of Genetic Algorithms: Part 1, Fundamentals
• An Overview of Genetic Algorithms: Part 2, Research Topics
• An Introduction to Genetic Algorithms, Melanie Mitchell
  1996, MIT Press, Cambridge, Massachusetts.
• Genetic algorithms for modelling and optimisation, John McCall, Journal of Computational and Applied Mathematics 184 (2005) 205 – 222.
• Comparison of genetic sequencing operators (useful for the Traveling Salesman Problem)
• A Comparison of Genetic Sequencing Operators
• A list of genetic operations (crossover and mutation)


• C code of genetic operations for binary data using bitwise operators (one-point two-point and uniform crossover; mutation in one place and bit flip mutation)
• C code of random bits generation for good random integers
• Genetic algorithms for shop scheduling problems: a survey, Frank Werner.

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

Compulsory Assignment

Simulated Annealing

• Basic bibliography
• Optimization by simulated annealing (post by dcoetzee on March 19, 2009)
• Comprehensive introduction to Simulated Annealing
• Simulated Annealing, weighted simulated annealing and genetic algorithm at work
  François Bergeret and Philippe Besse
  and an implementation of the algorithm.
• A simple implementation of the SA algorithm for a complicate function in one variable(click here for a version in pdf)
• Numerical Recipes in C. The Art of Scientific Computing: Section 10.9
• Some interesting links from the wikipedia page
• Simulated Annealing visualization A visualization of a simulated annealing solution to the N-Queens puzzle by Yuval Baror.
• Image evolution Online demonstration. This is a debatable implementation of SA, being more like a hill climbing algorithm.
• C++ SA A simple C++ implementation of simulated annealing by Antonio Gulli
• Simulated Annealing A Java applet that allows you to experiment with simulated annealing. Source code included.
• Self-Guided Lesson on Simulated Annealing A Wikiversity project.

Optional Assignment

Ant colony algorithms

• Basic bibliography
• Ant colony Optimization Algorithms: Introduction and Beyond
  by Anirudh Shekhawat, Pratik Poddar and Dinesh Boswal.
• Ant colony optimization theory: A survey
  by Marco Dorigo and Christian Blum,
  Theoretical Computer Science 344 (2005) 243 – 278.
• Numeric example of ACS algorithm.
  Extracted from Ant Colony Optimization Solving the Traveling Salesman Problem by Kiril Matev.
• Concrete examples
• Classification With Ant Colony Optimization
• An adaptative genetic algorithm for multiprocessor task assignment problem with limited memory

Optional Assignment

Evaluation

• To comply with the university evaluation rules:
  • The compulsory assignment of Map routing (A* algorithm) is to be done in pairs.
  • All other assignments (compulsory or optional) are individual.
• The assignments will be delivered in Campus Virtual. Further instructions will be given.
• 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.
• If necessary there will be interviews to evaluate and discuss some of the assignments.
• The quality of the code of the program will be taken into account for the marks of the assignments and discussed in the interviews (if any).



Optimisation's web pages (of the Master's degree in Modelling for Science and Engineering and MathMods) corresponding to the previous courses


Academic year 2011/12, 2012/13, 2013/14, 2014/15, 2015/16, 2016/17, 2017/18, 2018/19, 2019/20 and 2020/21.



Back to the home page of Lluís Alsedà