Combinatorial Optimization

In the combinatorial optimization research line, we deal with the development of algorithms for the efficient solution of combinatorial optimization problems. While we mainly focus on the development and analysis of metaheuristics algorithms, we also do research in exact and mathehuristic approaches.


Combinatorial optimization problems are ubiquitous in the real-world. Routing, scheduling, location, or cutting/packing, are examples of common problems in this area. Most of these problems are characterized for having a complexity that makes it impossible to solve high-dimensional instances to optimality, and here is where metaheuristics algorithms come to play. Metaheuristic algorithms are a set of techniques and algorithms that, although in most of occasions do not guarantee to find the global optimal solutions, they provide high-quality solutions in affordable computation times. They account for high-level procedures to find, generate, or select simple heuristics, or elaborated methods where heuristics are hybridized with mathematical programming techniques.


In the heuristics optimization research line we develop new algorithms and techniques for the solution of combinatorial optimization problems. Particularly, in the last years we have carried out research in the areas of population-based algorithms and local-search strategies. In population-based algorithms we have concentrated in estimation of distribution algorithms and particularly in their use on the solution of permutation-based combinatorial optimization problems. In the case of local-search algorithms, several of our research results in the analysis of their behavior have contributed to the design of new local search methods.

In addition to the previous work we also pursue theoretical analysis of metaheuristic algorithms and its application on the solution of real-world problems. Specifically, we have lately considered spacecraft trajectory design, routing problems, production planning or logistics for emergency medical services.

Another piece of research that is also carried out in the line is the development of exact algorithms. Particularly we try to make contributions to i) branch-and-bound and branch-and-cut strategies, ii) research in stochastic optimization and risk management and iii) design and implementation of decomposition algorithms based on Branch and Fix Coordination and Lagrangean techniques.