Exact methods for hard problems

Marina Leal Palazón
Moisés Rodríguez Madrena
Instituto de Matemáticas de la Universidad de Sevilla (IMUS)
Federico Perea Rojas-Marcos
Event type

The non-polynomial complexity of some combinatorial optimization problems have provoked a great success of the research in approximate methods. Among these methods, heuristics and metaheuristics are very popular, since (if well calibrated) they are able to yield near-optimal solutions to hard problems in a reasonable amount of time.
On the other hand, exact methods guarantee the optimal solution, if enough computational time is allowed. The main drawback of these methods is that the time allowed is not always enough, even to find a feasible solution! Despite this, even for hard problems, efforts in designing good exact methods should not be neglected by default. Refinements in mathematical formulations, improvements in solvers and technology, make it possible for us to find optimal solutions to problems that could not be addressed in the past. In such case: why using an approximation method, if you can guarantee the optimal solution in a short time? In this talk, we will show how standard combinatorial optimization techniques allow us to solve realistic instances of a NP-hard problem.

Para recibir un certificado es necesario asistir al menos al 75% de las horas del curso y, además, inscribirse por correo electrónico a admin2-imus@us.es indicando lo siguiente:
Nombre de la actividad:
Nombre completo del participante:
DNI  o pasaporte:
Correo electrónico: