Relaxations and Heuristics

Many real-life optimization problems are NP-hard. For these problems, it is not known whether there exist efficient algorithms to determine an optimal solution within a reasonable amount of time. In this course, we will focus on providing lower and upper bounds for the objective function values of such problems by studying relaxations and heuristics.

On the one hand, several methods are discussed which are able to obtain dual bounds (upper bounds on the optimal value of maximization problems) and, on the other hand, we will discuss ways to find good feasible solutions that provide primal (lower) bounds.

We will discuss the following topics:

• ILP formulations

• Branch-and-bound

• Cutting planes, valid inequalities, polyhedra en facets

• Column generation

• Local search heuristics, metaheuristics, heuristics based on integer programming

• Approximation algorithms