Optimisation (2014/15)

C learning

Combinatorial Algorithms for graphs

• General definitions and searches on graphs
• Graph Theory: Introduction
• Glossary of Graph Theory
• Search in Graphs: Depth-first: Wikipedia (the three orderings for binary trees) Lecture by Rashid Bin Muhammad.
• Search in Graphs: Breadth-first: Wikipedia Lecture by Rashid Bin Muhammad.
• Tree traversal: an easier view.
• Greedy algorithm
• Dijkstra Algorithm for optimum paths on graphs
• 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
• A* Algorithm: Heuristic search for optimum paths on graphs
• 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.
• A* Algorithm (correct version)

Assignments:

Dijkstra Algorithm (recommended):

Solve the project proposed here.

A* Algorithm (compulsory):

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

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.
• 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)
• Genetic algorithms for shop scheduling problems: a survey, Frank Werner.

Assignments:

First exercise (compulsory part): Vertex coloring of graphs.

Second exercise (optional part): Maximization of a (complicate and artificial) function by a genetic algorithm

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

Assignments:

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.

Assignments

Scheduling

• Introductory examples
• Combinatorial Scheduling Theory, Ronald L. Graham; a classical paper.
• Deterministic Scheduling Theory, R. Gary Parker, Chapman Hall
  Pages: 1-13.
• Deterministic Scheduling, Krzysztof Giaro, Gdańsk University of Technology
• Basic bibliography
• Optimization and approximation in deterministic sequencing and scheduling: a survey, R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Khan.
• Scheduling Algorithms, Peter Brucker
  Springer-Verlag, 2007, Berlin Heidelberg New York (ISBN 978-3-540-69515-8).
• An adaptative genetic algorithm for multiprocessor task assignment problem with limited memory
• University Course Timetabling Using ACO: A Case Study on Laboratory Exercises
• Solving scheduling problems by simulated annealing
• Notation for theoretic scheduling problems

Evaluation

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