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

The final grade consists of the following parts:

• Final written exam (50%)

• Project (50%)

For both the exam and project, your grade should be a 5 or higher to pass the course.

Final grade calculation: (0.5 * written exam) + (0.5 * project)

Resit/ Repair opportunities:

In case of an insufficient result, repair opportunities may be offered in accordance with TER Implementation Regulations Art 5, sub 5., for:

- Written exam: written resit

- Project: resubmit deliverable

Disclaimer: information may change depending on unforeseen circumstances or measures (see: TER Art 29, sub 4).