Operational Research (06POGROP)

• Coefficient : 1.5
• Hourly Volume: 33h (including 18h supervised)
  CTD : 9h supervised (and 1.5h unsupervised)
  Labo : 9h supervised (and 1.5h unsupervised)
  Out-of-schedule personal work : 12h

AATs Lists

Description

1. Graph traversal
   • depth traversal
   • width traversal
   • links with FIFO/LIFO
2. Paths in graphs
   • with paths
   • Roy-Warshall algorithm
   • Dijkstra algorithm
3. Commercial traveller
   • problem statement, reductions
   • "brute force" solution
   • notions of algorithmic complexity
4. Optimisation
   • notion of heuristics
   • backtracking algorithms
   • branch and bound algorithms

Learning Outcomes AAv (AAv)

• AAv1 [heures: 15, B2,B3] : At the end of the course, each student will be able to correctly apply the relevant mathematical tools to solve problems involving the calculation of optimal paths (depth, width, shortest via Ford or Dijkstra) in directed or undirected, valuated or valueless graphs.

• AAv2 [heures: 15, B2,B3] : At the end of the course, each student will be able to correctly apply the relevant mathematical tools to solve flow maximisation problems in a transport network, taking possible costs into account.

Assessment methods

average of several short continuous assessments from CTD (coefficient 1) and Lab (coefficient 1)

Key Words

Operational research, optimisation, travelling salesman, tree traversal, graph traversal graph traversal, width traversal, depth traversal, Dijkstra algorithm, Roy-Warshall algorithm algorithm, backtracking, branch and bound.

Prerequisites

Knowledge of one or more programming languages and a minimum understanding of basic basic tools such as arrays, lists, recursive functions, etc. recursive functions, etc.

Resources

The course is based on close interaction with a practical project. All the tools used are free and open-source.