Combinatorial optimisation problems appear in a very impressive number of diverse contexts, both of a practical and theoretical nature. In actual applications, combinatorial optimisation is necessary in order to solve problems concerning logistics, planning, routing, scheduling, personnel shifts, network design, shipping and storage of goods, etc. In the field of discrete mathematics, many combinatorial problems have a remarkable theoretical interest. In particular, many of those problems are defined within the context of the graph theory.

Almost invariably, the combinatorial optimisation problems we deal with turn out to be very complex from the computational point of view (in technical parlance, they are NP-hard). The solution of these problems requires sophisticated algorithms, usually based on the modelling of the problem through mathematical programming techniques. Our group studies problems of this nature mainly in relation with the scheduling of machines and personnel in the productive/industrial environment and with applications in the field of molecular biology, such as the prediction and comparison of three-dimensional protein structures, the calculation of evolutionary distances, the extraction of common patterns, etc. In order to solve these problems we typically use an approach based on Integer Linear Programming, with sophisticated branch-and-bound techniques, through cutting planes in order to reach the exact solution of instances having an actual interest within a reasonable time. For particularly difficult problems we also use heuristic techniques, such as Tabu Search or Genetic Algorithms, which, even though they cannot guarantee the optimal solution, on average are able to produce high-quality solutions. A further research thread we pursue is the study and advancement of the basic theory of mathematical programming, such as, for instance, the use of general-purpose inequalities we introduced (local search inequalities) within the scope of several problems, or the (compact) polynomial reformulation of models having an exponential number of constraints and/or variables. We are also interested in the area of approximation algorithms and in the use of Integer Programming in order to deal with open problems and conjectures on suitable combinatorial structures.