LINFO2266: Advanced Algorithms for Optimization

Welcome to the course website for LINFO2266: Advanced Algorithms for Optimization at UCLouvain.

This graduate-level course focuses on practical and theoretical concepts for solving challenging combinatorial optimization problems. You will study and implement foundational algorithms across major optimization paradigms:

• Dynamic Programming (DP): State space modeling, memoization, and Bellman equations.

• Branch and Bound (BnB): Systematic state exploration and tree pruning.

• Lagrangian Relaxation: Mathematical bounds and Held-Karp relaxation for the TSP.

• Linear Programming (LP) & Simplex: Polyhedral formulation and simplex pivoting.

• Network Flows & Maximum Matching: Graph-based flow formulations.

• Local Search: Metaheuristics, neighborhoods (k-opt), tabu search, and candidate list strategies.

• Constraint Programming (CP): Filtering algorithms, domain consistency, and symmetry breaking.

• Decision Diagrams (MDD): Branch-and-bound with relaxed and restricted Multi-valued Decision Diagrams.

Course Contents

• 1. Organization
  • 1.1. Pedagogy
  • 1.2. Resources and Material
  • 1.3. Evaluation
  • 1.4. Tools
  • 1.5. Projects and submissions
  • 1.6. Contact and communication
• 2. Dynamic Programming
  • 2.1. Theory
  • 2.2. Project: Dynamic Programming
• 3. Benchmarking and Comparing Optimization Algorihtms
  • 3.1. Theory
• 4. Branch and Bound
  • 4.1. Theory
  • 4.2. Project: Branch and Bound, Lagrangian Relaxation
• 5. Lagrangian Relaxation
  • 5.1. Theory
• 6. Linear Programming
  • 6.1. Theory
  • 6.2. Project: Linear Programming and Maximum-Flows
• 7. Network Flows
  • 7.1. Theory
• 8. Local Search
  • 8.1. Theory
  • 8.2. Project : TSP with Local Search
• 9. CP
  • 9.1. Theory
  • 9.2. Project : Constraint Programming
• 10. DP with A* based search
  • 10.1. Theory
  • 10.2. Project : A*
• 11. Competition
  • 11.1. Theory