Christian Blum, IIIA-CSIC researcher, awarded with a SEIO-BBVA Foundation prize.A study carried out by researchers from the Artificial Intelligence Research Institute (IIIA-CSIC), Universidad de la Concepción, The University of Manchester and the University of the Basque Country, have developed a new general algorithm for combinatorial optimization.
This awarded research has developed a hybrid algorithm that combines algorithmic components from the metaheuristic field with exact techniques from the operations research (OR) field in a novel way
On one hand, a metaheuristic is a general algorithmic concept, something like a set of instructions for a recipe, for solving optimization problems. On the other hand, OR is a branch of Applied Mathematics. This research’s innovation is precisely brought forward by the hybridization of both techniques.
The purpose of this new technique is to design better combinatorial optimization engines to resolve problems, which is key in many industrial and educational settings.
An example where this could be helpful are vehicle routing problems: picture a logistics company with one or more depots for its fleet of vehicles and one or more warehouses for storing the goods. Each day goods must be delivered to clients with respect to the orders they have placed. This means, deliveries must be assigned to vehicles, and optimal routes must be found for the vehicles in order to save fuel and time.
As finding the best valid solution with respect to quality is often not possible, metaheuristics techniques aim at finding "good-enough" solutions in a reasonable computation time. Moreover, some of them start with some valid solutions and repeatedly apply small changes with the aim of obtaining improved solutions.
Concerning optimization, much of the efforts in OR have been dedicated to the development of exact techniques, that is, mathematical techniques for optimization that are able to derive provenly optimal solutions.
Nevertheless, these techniques reach their limits with growing problem size, depending on the problem’s characteristics. This is when researchers and practitioners usually turn towards approximate algorithms such as heuristics or metaheuristics, which are developed not only in OR but also, for example, in Artificial Intelligence. They can give very good solutions (although not always optimal) in a shorter computation time.
Christian Blum (IIIA-CSIC), one of the awarded researchers, claims that “about 20 years ago researchers started to look at combinations, or hybridizations, of algorithms of different types. The optimization technique for which we received the SEIO-BBVA Foundation award -called CMSA- is such a hybrid algorithm between metaheuristics and OR techniques. It intends to combine the best of both to make a more reliable optimization process. It is fair to say that, nowadays, (hybrid) metaheuristic techniques are state of the art for many real-life optimization problems.”
The SEIO-BBVA Foundation award
On winning this award, Christian Blum says that “it causes enormous professional satisfaction. As a researcher you are used to failure. This is quite natural, because often we step into uncharted territories and we do not know beforehand how things will turn out. From this point of view, we especially value those occasions in which we are successful. The development of the CMSA algorithm is certainly such a success.”
SEIO-BBVA Foundation awards were created in 2020 and they are the only awards at national level specifically dedicated to contributions from the OR and the statistics field. For this reason, they are considered to be "among the most important awards" of this type for all researchers working in OR and/or statistics.
Alongside Christian Blum other researchers involved in this research have been Pedro Pinacho (Universidad de la Concepción, Chile), Manuel López-Ibáñez (The University of Manchester, United Kingdom) and José A. Lozano (University of the Basque Country).