COURSE OBJECTIVES

Treating difficult combinatorial optimization problems with the help of constraint programming and local search techniques.

TARGET AUDIENCE

Engineers, economists, scientists and developers interested in modeling decision problems and implementing optimization algorithms.

Constraint Programming
• Constraint Programming: principles and applications.
• Presentation of a constraint programming solver: Xpress-Kalis.

Practical applications of constraint programming
• A simple staff scheduling example.
• Solving a movie scenes allocation problem.
• Solving a frequency assignment problem.
• Enumeration configuration – Branching strategies – Definition of search strategies for an advanced user.

Local Search
• Intuition (n-queens) – Neighborhood (car-sequencing, magic square) – Optimization (warehouse location) – 2-opt, k-opt.
• Optimality vs. Feasibility (graph coloring) – Complex neighborhood (sport scheduling) – Escaping from local minima, connectivity.
• Formalization, heuristics – Introduction to metaheuristics: Variable Neighborhood Search, Simulated annealing, Tabu search.

Scheduling problems and resource management
• Introduction to scheduling problems.
• Disjunctive scheduling – application to the construction of a sports stadium.
• Multi-machines disjunctive scheduling – Job Shop problem.
• Cumulative scheduling – non-renewable resources.