Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 25
Encontrada(s) 1 página(s)

DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

AntNetAlign: Ant Colony Optimization for Network Alignment

  • Rodríguez-Corominas, Guillem
  • Blum, Christian
  • Blesa, María Jesús
Network Alignment (NA) is a hard optimization problem with important applications such as, for example, the identification of orthologous relationships between different proteins and of phylogenetic relationships between species. Given two (or more) networks, the goal is to find an alignment between them, that is, a mapping between their respective nodes such that the topological and functional structure is well preserved. Although the problem has received great interest in recent years, there is still a need to unify the different trends that have emerged from diverse research areas. In this paper, we introduce AntNetAlign, an Ant Colony Optimization (ACO) approach for solving the problem. The proposed approach makes use of similarity information extracted from the input networks to guide the construction process. Combined with an improvement measure that depends on the current construction state, it is able to optimize any of the three main topological quality measures. We provide an extensive experimental evaluation using real-world instances that range from Protein–Protein Interaction (PPI) networks to Social Networks. Results show that our method outperforms other state-of-the-art approaches in two out of three of the tested scores within a reasonable amount of time, specially in the important score. Moreover, it is able to obtain near-optimal results when aligning networks with themselves. Furthermore, in larger instances, our algorithm was still able to compete with the best performing method in this regard., Christian Blum and Guillem Rodríguez Corominas, Spain were supported by grants PID2019-104156GB-I00 and TED2021-129319B-I00 funded by MCIN/AEI/10.13039/501100011033. Maria J. Blesa acknowledges support from AEI, Spain under grant PID-2020-112581GB-C21 (MOTION) and the Catalan Agency for Management of University and Research Grants (AGAUR), Spain under grant 2017-SGR-786 (ALBCOM)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Ant colony optimization: a bibliometric review

  • Blum, Christian
This paper is a follow-up of one of the most-cited articles published in the first 20 years of the existence of Physics of Life Reviews. The specific topic is “ant colony optimization”, which is a metaheuristic for solving challenging optimization problems. Due to its inspiration from natural ant colonies' shortest path-finding behavior, this optimization technique forms part of a larger field known as swarm intelligence. After a short introduction to ant colony optimization, we first provide a chronology focusing on algorithmic developments rather than applications. The main part of the paper deals with a bibliometric study of the ant colony optimization literature. Interesting trends concerning, for example, the geographic origin of publications and the change in research focus over time, can be learned from the presented graphs and numbers., The research presented in this paper was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

CMSA based on set covering models for packing and routing problems

  • Akbay, Mehmet Anıl
  • Blum, Christian
  • Kalayci, Can Berk
Many packing, routing, and knapsack problems can be expressed in terms of integer linear programming models based on set covering. These models have been exploited in a range of successful heuristics and exact techniques for tackling such problems. In this paper, we show that integer linear programming models based on set covering can be very useful for their use within an algorithm called “Construct, Merge, Solve & Adapt”(CMSA), which is a recent hybrid metaheuristic for solving combinatorial optimization problems. This is because most existing applications of CMSA are characterized by the use of an integer programming solver for solving reduced problem instances at each iteration. We present applications of CMSA to the variable-sized bin packing problem and to the electric vehicle routing problem with time windows and simultaneous pickups and deliveries. In both applications, CMSA based on a set covering model strongly outperforms CMSA when using an assignment-type model. Moreover, state-of-the-art results are obtained for both considered optimization problems., The research presented in this paper was supported by Grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033. Additionally, M.A. Akbay and C.B. Kalayci acknowledge support from the Technological Research Council of Turkey (TUBITAK) under Grant no. 119M236., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Extension of CMSA with a learning mechanism: application to the far from most string problem

  • Pinacho Davidson, Pedro
  • Blum, Christian
  • Pinninghoff, M. Angélica
  • Contreras, Ricardo
One of the problems with exact techniques for solving combinatorial optimization problems is that they tend to run into problems with growing problem instance size. Nevertheless, they might still be very usefully employed, even in the context of large problem instances, as a sub-ordinate method within so-called hybrid metaheuristics. “Construct, Merge, Solve and Adapt” (Cmsa) is a hybrid metaheuristic technique that allows the application of exact methods to large-scale problem instances through intelligent instance reduction. However, Cmsa does not make use of an explicit learning mechanism. In this work, an algorithm called LEARN_CMSA is presented for the application to the far from most string problem (FFMSP), which is an NP-hard combinatorial optimization problem from the field of string consensus problems. LEARN_CMSA results from hybridization between Cmsa and a population-based algorithm. By means of this hybridization, explicit learning is introduced to Cmsa. Even though the FFMSP is a well-studied problem, LEARN_CMSA achieves superior performance when compared to current state-of-the-art solvers., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. P. Pinacho-Davidson acknowledges financial support from FONDECYT through grant number 11230359. C. Blum was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

A neural network based guidance for a BRKGA: an application to the longest common square subsequence problem

  • Reixach, Jaume
  • Blum, Christian
  • Đukanović, Marko
  • Raidl, Günther R.
24th European Conference, EvoCOP 2024 Held as Part of EvoStar 2024 Aberystwyth, UK, April 3–5, 2024, Proceedings, Thomas Stützle, Markus Wagner, editors, In this work we apply machine learning to better guide a biased random key genetic algorithm (Brkga) for the longest common square subsequence (LCSqS) problem. The problem is a variant of the well-known longest common subsequence (LCS) problem in which valid solutions are square strings. A string is square if it can be expressed as the concatenation of a string with itself. The original Brkga is based on a reduction of the LCSqS problem to the LCS problem by cutting each input string into two parts. Our work consists in enhancing the search process of Brkga for good cut points by using a machine learning approach, which is trained to produce promising cut points for the input strings of a problem instance. In this study, we show the benefits of this approach by comparing the enhanced Brkga with the original Brkga, using two benchmark sets from the literature. We show that the results of the enhanced Brkga significantly improve over the original results, especially when tackling instances with non-uniformly generated input strings., Jaume Reixach and Christian Blum are supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033. G¨unter R. Raidl is supported by the Vienna Graduate School on Computational Optimization (VGSCO), Austrian Science Foundation, project no. W1260-N35. Marko Djukanovi´c is supported by the project entitled “Development of artificial intelligence models and algorithms for solving difficult combinatorial optimization problems” funded by the Ministry of Scientific and Technological Development and the Higher Education of the Republic of Srpska., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Construct, Merge, Solve & Adapt : A Hybrid Metaheuristic for Combinatorial Optimization

  • Blum, Christian
XVI, 192, 15 b/w illustrations, 43 illustrations in colour., This book describes a general hybrid metaheuristic for combinatorial optimization labeled Construct, Merge, Solve & Adapt (CMSA). The general idea of standard CMSA is the following one. At each iteration, a number of valid solutions to the tackled problem instance are generated in a probabilistic way. Hereby, each of these solutions is composed of a set of solution components. The components found in the generated solutions are then added to an initially empty sub-instance. Next, an exact solver is applied in order to compute the best solution of the sub-instance, which is then used to update the sub-instance provided as input for the next iteration. In this way, the power of exact solvers can be exploited for solving problem instances much too large for a standalone application of the solver., During the time of writing this book, the author was supported as principal investigator of the following three grants funded by MCIN/AEI/10.13039/501100011033: PID2019-104156GB-I00, PID2022-136787NB-I00, and TED2021-129319B-I00., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Efficient Search Algorithms for the Restricted Longest Common Subsequence Problem

  • Djukanović, Marko
  • Kartelj, Aleksandar
  • Eftimov, Tome
  • Reixach, Jaume
  • Blum, Christian
En Computational Science – ICCS 2024, 24th International Conference, Malaga, Spain, July 2–4, 2024, Proceedings, Part V.- Conference proceedings., This paper deals with the restricted longest common subsequence (RLCS) problem, an extension of the well-studied longest common subsequence problem involving two sets of strings: the input strings and the restricted strings. This problem has applications in bioinformatics, particularly in identifying similarities and discovering mutual patterns and motifs among DNA, RNA, and protein molecules. We introduce a general search framework to tackle the RLCS problem. Based on this, we present an exact best-first search algorithm and a meta-heuristic Beam Search algorithm. To evaluate the effectiveness of these algorithms, we compare them with two exact algorithms and two approximate algorithms from the literature along with a greedy approach. Our experimental results show the superior performance of our proposed approaches. In particular, our exact approach outperforms the other exact methods in terms of significantly shorter computation times, often reaching an order of magnitude compared to the second-best approach. Moreover, it successfully solves all problem instances, which was not the case with the other approaches. In addition, Beam Search provides close-to-optimal solutions with remarkably short computation times., The research of M. Djukanović is partially supported by the Ministry for Scientific and Technological Development and Higher Education of the Republic of Srpska, B &H in the course of the bilateral research project between B &H and Slovenia entitled “Theoretical and computational aspects of some graph problems with the application to graph network information spreading” and the COST Action ROAR-NET under no. CA22137. A. Kartelj was supported by grant 451-03-47/2023-01/200104 funded by the Ministry of Science Technological Development and Innovations of the Republic of Serbia. J. Reixach and C. Blum are supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Extending CMSA with Reinforcement Learning: Application to Minimum Dominating Set

  • Reixach, Jaume
  • Blum, Christian
This volume constitutes the refereed proceedings of Metaheuristics on 15th International Conference, MIC 2024, held in Lorient, France, during June 4–7, 2024.- The 36 full papers presented together with 34 short papers were carefully reviewed and selected from 127 submissions. The conference focuses on artificial intelligence, combinatorial optimization, computer science, graph theory, evolutionary algorithms, genetic algorithms, simulated annealing, optimization, optimization problems., This work leverages reinforcement learning for designing a new variant of Construct, Merge, Solve and Adapt (CMSA), a rather new hybrid metaheuristic for combinatorial optimization. We demonstrate a twofold improvement over the standard CMSA. Firstly, the new variant simplifies CMSA by eliminating the need for a greedy function to probabilistically generate solutions. Additionally, it performs better, as we demonstrate in the context of the Minimum Dominating Set (MDS) problem., The research presented in this paper was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Large Language Models for the Automated Analysis of Optimization Algorithms

  • Chacón Sartori, Camilo
  • Blum, Christian
  • Ochoa, Gabriela
GECCO '24: Genetic and Evolutionary Computation Conference, July 14 - 18, 2024, VIC, Melbourne, Australia., The ability of Large Language Models (LLMs) to generate high-quality text and code has fuelled their rise in popularity. In this paper, we aim to demonstrate the potential of LLMs within the realm of optimization algorithms by integrating them into STNWeb. This is a web-based tool for the generation of Search Trajectory Networks (STNs), which are visualizations of optimization algorithm behavior. Although visualizations produced by STNWeb can be very informative for algorithm designers, they often require a certain level of prior knowledge to be interpreted. In an attempt to bridge this knowledge gap, we have incorporated LLMs, specifically GPT-4, into STNWeb to produce extensive written reports, complemented by automatically generated plots, thereby enhancing the user experience and reducing the barriers to the adoption of this tool by the research community. Moreover, our approach can be expanded to other tools from the optimization community, showcasing the versatility and potential of LLMs in this field., C. Chacón and C. Blum were supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/ 501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

STNWeb for the analysis of optimization algorithms: a short introduction

  • Chacón Sartori, Camilo
  • Blum, Christian
This volume constitutes the refereed proceedings of Metaheuristics on 15th International Conference, MIC 2024, held in Lorient, France, during June 4–7, 2024., Ponencia de conferencia., In the realm of optimization, where intricate landscapes conceal possibly hidden pathways to high-quality solutions, STNWeb serves as a beacon of clarity. This novel web-based visualization platform empowers researchers to delve into the intricate interplay between algorithms and optimization problems, uncovering the factors that influence algorithm performance across diverse problem domains, be they discrete/combinatorial or continuous. By leveraging the inherent power of visual data representation, STNWeb transcends traditional analytical methods, providing a robust foundation for dissecting algorithm behavior and pinpointing the mechanisms that elevate one algorithm above another. This visually-driven approach fosters a deeper understanding of algorithmic strengths and weaknesses, ultimately strengthening the discourse surrounding algorithm selection and refinement for complex optimization tasks., The research presented in this paper was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Two Examples for the Usefulness of STNWeb for Analyzing Optimization Algorithm Behavior

  • Akbay, Mehmet Anıl
  • Blum, Christian
15th International Conference, MIC 2024, Lorient, France, June 4–7, 2024, Proceedings, Part II., Search Trajectory Networks (STNs) are visualizations of directed graphs designed to analyze the behavior of stochastic optimization algorithms such as metaheuristics. Their purpose is to provide researchers with a tool that allows them to gain a deeper understanding of the behavior exhibited by multiple algorithms when applied to a specific instance of an optimization problem. In this short paper, we present two examples of our work in which STN graphics have helped us to discover interesting and useful algorithm/problem characteristics., The research presented in this paper was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Integrating multi-armed bandit with local search for MaxSAT

  • Zheng, Jiongzhi
  • He, Kun
  • Zhou, Jianrong
  • Jin, Yan
  • Li, Chu Min
  • Manyà, Felip
Partial MaxSAT (PMS) and Weighted PMS (WPMS) are two practical generalizations of the MaxSAT problem. In this paper, we introduce a new local search algorithm for these problems, named BandHS. It applies two multi-armed bandit (MAB) models to guide the search directions when escaping local optima. One MAB model is combined with all the soft clauses to help the algorithm select to satisfy appropriate soft clauses, while the other MAB model is combined with all the literals in hard clauses to help the algorithm select suitable literals to satisfy the hard clauses. These two models enhance the algorithm's search ability in both feasible and infeasible solution spaces. BandHS also incorporates a novel initialization method that prioritizes both unit and binary clauses when generating the initial solutions. Moreover, we apply our MAB approach to the state-of-the-art local search algorithm NuWLS and to the local search component of the incomplete solver NuWLS-c-2023. The extensive experiments conducted demonstrate the excellent performance and generalization capability of the proposed method. Additionally, we provide analyses on the type of problems where our MAB method works well or not, aiming to offer insights and suggestions for its application. Encouragingly, our MAB method has been successfully applied in core local search components in the winner of the WPMS complete track of MaxSAT Evaluation 2023, as well as the runners-up of the incomplete track of MaxSAT Evaluations 2022 and 2023., This work is supported by National Natural Science Foundation of China (U22B2017), Microsoft Research Asia (100338928), and grants PID2019-111544GB-C21, PID2022-139835NB-C21 and TED2021-129319B-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Metaheuristics and Large Language Models Join Forces: Toward an Integrated Optimization Approach

  • Chacón Sartori, Camilo
  • Blum, Christian
  • Bistaffa, Filippo
  • Rodríguez-Corominas, Guillem
Since the rise of Large Language Models (LLMs) a couple of years ago, researchers in metaheuristics (MHs) have wondered how to use their power in a beneficial way within their algorithms. This paper introduces a novel approach that leverages LLMs as pattern recognition tools to improve MHs. The resulting hybrid method, tested in the context of a social network-based combinatorial optimization problem, outperforms existing state-of-the-art approaches that combine machine learning with MHs regarding the obtained solution quality. By carefully designing prompts, we demonstrate that the output obtained from LLMs can be used as problem knowledge, leading to improved results. Lastly, we acknowledge LLMs' potential drawbacks and limitations and consider it essential to examine them to advance this type of research further. Our method can be reproduced using a tool available at: https://github.com/camilochs/optipattern., This work was supported by MCIN/AEI/10.13039/ 501100011033 under Grant TED2021-129319B-I00 and Grant PID2022-136787NB-I00., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

A Biased Random Key Genetic Algorithm for Solving the Longest Common Square Subsequence Problem

  • Reixach, Jaume
  • Blum, Christian
  • Djukanovic, Marko
  • Raidl, Gunther R.
This article considers the longest common square subsequence (LCSqS) problem, a variant of the longest common subsequence (LCS) problem in which solutions must be square strings. A square string can be expressed as the concatenation of a string with itself. The LCSqS problem has applications in bioinformatics, for discovering internal similarities between molecular structures. We propose a metaheuristic approach, a biased random key genetic algorithm (BRKGA) hybridized with a beam search (BS) from the literature. Our approach is based on reducing the LCSqS problem to a set of promising LCS problems. This is achieved by cutting each input string into two parts first and then evaluating such a transformed instance by solving the LCS problem for the obtained overall set of strings. The task of the BRKGA is, hereby, to find a set of good cut points for the input strings. For this purpose, the search is carefully biased by problem-specific greedy information. For each cut point vector, the resulting LCS problem is approximately solved by the existing BS approach. The proposed algorithm is evaluated against a previously proposed state-of-the-art variable neighborhood search (VNS) on random uniform instances from the literature, new nonuniform instances, and a real-world instance set consisting of DNA strings. The results underscore the importance of our work, as our novel approach outperforms former state-of-the-art with statistical significance. Particularly, they evidence the limitations of the VNS when solving nonuniform instances, for which our method shows superior performance., MCIN/AEI/10.13039/501100011033 (Grant Number: TED2021-129319B-I00 and PID2022-136787NB-I00) Vienna Graduate School on Computational Optimization (VGSCO), Austrian Science Foundation (Grant Number: W1260-N35), Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Accelerating the k-Means++ Algorithm by Using Geometric Information

  • Rodríguez Corominas, Guillem
  • Blesa, Maria J.
  • Blum, Christian
Clustering is a fundamental task in data analysis with applications across a wide range of fields, such as computer vision, pattern recognition, and data mining. Real-world use cases include social network analysis, medical imaging, market segmentation, and anomaly detection, to name a few. In this paper, we propose an acceleration of the exact k-means++ algorithm using geometric information, specifically the Triangle Inequality and additional norm filters, along with a two-step sampling procedure. Our experiments demonstrate that the accelerated version outperforms the standard k-means++ version in terms of the number of visited points and distance calculations, achieving greater speedup as the number of clusters increases. The version utilizing the Triangle Inequality is particularly effective for low-dimensional data, while the additional norm-based filter enhances performance in high-dimensional instances with greater norm variance among points. Additional experiments show the behavior of our algorithms when executed concurrently across multiple jobs and examine how memory performance impacts practical speedup., This work was supported in part by the Department of Research and Universities of the Government of Catalonia by means of an European Social Fund (ESF)-Founded Pre-Doctoral Grant of the Catalan Agency for Management of University and Research Grants (AGAUR) under Grant 2022 FI_B 00903, in part by the Agencia Estatal de Investigación (AEI) under Grant PID-2020-112581GB-C21 (MOTION), in part by Ministerio de Ciencia e Innovación (MCIN)/AEI/10.13039/501100011033 under Grant TED2021-129319B-I00 and Grant PID2022-136787NB-I00, and in part by the European Commission–NextGenerationEU, through Momentum CSIC Programme: Develop Your Digital Talent, under Project MMT24-IIIA-02., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

A learning search algorithm for the Restricted Longest Common Subsequence problem

  • Djukanović, Marko
  • Reixach, Jaume
  • Nikolikj, Ana
  • Eftimov, Tome
  • Kartelj, Aleksandar
  • Blum, Christian
This paper addresses the Restricted Longest Common Subsequence (RLCS) problem, an extension of the well-known Longest Common Subsequence (LCS) problem. This problem has significant applications in bioinformatics, particularly for identifying similarities and discovering mutual patterns and important motifs among DNA, RNA, and protein sequences. Building on recent advancements in solving this problem through a general search framework, this paper introduces two novel heuristic approaches designed to enhance the search process by steering it towards promising regions in the search space. The first heuristic employs a probabilistic model to evaluate partial solutions during the search process. The second heuristic is based on a neural network model trained offline using a genetic algorithm. A key aspect of this approach is extracting problem-specific features of partial solutions and the complete problem instance. An effective hybrid method, referred to as the learning beam search, is developed by combining the trained neural network model with a beam search framework. An important contribution of this paper is found in the generation of real-world instances where scientific abstracts serve as input strings, and a set of frequently occurring academic words from the literature are used as restricted patterns. Comprehensive experimental evaluations demonstrate the effectiveness of the proposed approaches in solving the RLCS problem. Finally, an empirical explainability analysis is applied to the obtained results. In this way, key feature combinations and their respective contributions to the success or failure of the algorithms across different problem types are identified., The research of M. Djukanović is partially supported by the Ministry for Scientific and Technological Development and Higher Education of the Republic of Srpska, B&H in the course of the bilateral research project between B&H and Slovenia entitled “Theoretical and computational aspects of some graph problems with the application to graph network information spreading” under project no. 1259084 and the project “Application of deep learning in improving the efficiency of optimization algorithms” under project no. 1259114. A. Kartelj was supported by grant 451-03-47/2023-01/200104 funded by the Ministry of Science Technological Development and Innovations of the Republic of Serbia. J. Reixach and C. Blum are supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033. A. Nikolikj and T. Eftimov acknowledge the support of the Slovenian Research and Innovation Agency through program grant P2-0098, project grants No. J2-4460 and No. GC-0001, BI-BA/24-25-006, and young researcher grant No. PR-12897 to AN. This work is also funded by the European Union under Grant Agreement 101187010 (HE ERA Chair AutoLearn-SI). The authors would like to acknowledge the use of the Computing Cluster Unit of the Institute of Logic and Computation at the Vienna University of Technology for this research project., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

SoftBinReduce: data reduction for color quantization through soft binning

  • Rodríguez-Corominas, Guillem
  • Blesa Aguilera, María Jesús;
  • Blum, Christian
For detailed results, interested parties can request information from the corresponding author. The CQ100 dataset used for the experimental evaluation is available at https://doi.org/10.17632/vw5ys9hfxw.2. The USC-SIPI dataset is available at https://sipi.usc.edu/database/database.php?volume=misc. The Kodak dataset is available at: https://r0k.us/graphics/kodak., In this paper, we propose SoftBinReduce, a data reduction method for Color Quantization. Our approach consists of four main steps: (1) identifying representatives in each channel, (2) generating three-dimensional bins, (3) distributing pixel values using a soft binning technique, and (4) repositioning the resulting bins. Additionally, we introduce an adapted Sort-Means algorithm for the Pixel Mapping phase, providing a strong initial guess. We conduct an extensive experimental evaluation primarily using the CQ100 dataset, but also the older Kodak and USC-SIPI datasets. We compare our method to two well-known data reduction techniques from the literature: pseudo-random and quasi-random sampling. The results demonstrate that our method outperforms both in terms of NMSE error versus the achieved speedup, particularly when the data is significantly reduced and with a higher number of colors in the generated palette. Moreover, an ablation study shows that all components of our method are necessary for producing high-quality results., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Guillem Rodríguez Corominas acknowledges support from the Department of Research and Universities of the Government of Catalonia by means of an ESF-founded pre-doctoral grant of the Catalan Agency for Management of University and Research Grants (AGAUR), under ref. number 2022 FI_B 00903. Maria J. Blesa acknowledges support from AEI under MICINN grant PID-2020-112581GB-C21 (MOTION). Christian Blum was supported by two grants funded by MCIN/AEI/10.13039/501100011033: TED2021-129319B-I00 and PID2022-136787NB-I00., We acknowledge administrative and technical support by the Spanish National Research Council (CSIC) and by the Universitat Politècnica de Catalunya (UPC)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Construct, merge, solve and adapt: Application to the minimum global domination problem

  • Blum, Christian
[Data availability] Concerning comprehensive results, individuals interested can request details from the corresponding author. The software and the problem instances are publicly available at https://github.com/ccblum/MGD_software.git., The CMSA algorithm for combinatorial optimization is a hybrid technique based on repeatedly solving sub-instances to the original problem instance. The incumbent sub-instance is extended at each iteration by the probabilistic generation of valid solutions to the original problem instance and by adding the components found in these solutions to the sub-instance. In addition, the incumbent sub-instance is reduced at each iteration by removing seemingly useless solution components. In recent years the usefulness of the CMSA algorithm has been shown by a range of applications to different combinatorial optimization problems. In this work, we provide a gentle introduction to CMSA by describing the application to the so-called minimum global domination problem as an example., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. The author was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

AntNetAlign—A software package for Network Alignment

  • Rodríguez-Corominas, Guillem
  • Blesa, María Jesús
  • Blum, Christian
Original software publication., In this paper we introduce AntNetAlign, an open-source tool (written in C++) that implements an Ant Colony Optimization (ACO) for solving the Network Alignment (NA) problem, a well-known hard optimization problem with important applications in different areas, such as biology or social networks. Specifically, given two input networks, the tool finds an alignment between them (i.e., a mapping between the respective nodes) that optimizes one out of the three main topological measures. Additionally, it can make use of user-defined pairwise similarities between nodes during its construction phase, allowing for the use of more application-dependent information in order to increase its performance. Results show that AntNetAlign outperforms other state-of-the-art algorithms in two out of the three aforementioned topological scores within a reasonable amount of time, and is able to achieve competitive results in the context of larger instances (Rodríguez Corominas et al., 2023). Furthermore, a new version of the algorithm, which makes use of Negative Learning, was able to further improve these results, specially in the EC score (Corominas et al., 2022)., Guillem Rodríguez Corominas gets support from the Department of Research and Universities of the Government of Catalonia by means of an ESF-founded pre-doctoral grant of the Catalan Agency for Management of University and Research Grants (AGAUR, Catalonia, Spain), under ref. number 2022 FI_B 00903. Christian Blum was supported by two grants funded by MCIN/AEI/10.13039/501100011033: AEI, Spain PID2019-104156GB-I00, and TED2021-129319B-I00. Maria J. Blesa acknowledges support from AEI, Spain under grant PID-2020-112581GB-C21 (MOTION) and the Catalan Agency for Management of University and Research Grants (AGAUR , Catalonia, Spain), under grant 2021-SGR-01419 (ALBCOM)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

MaxSAT resolution for regular propositional logic

  • Coll, Jordi
  • Li, Chu Min
  • Manyà, Felip
  • Yangin, Elifnaz
[Data availability] No data was used for the research described in the article., Proof systems for SAT are unsound for MaxSAT because they preserve satisfiability but fail to preserve the minimum number of unsatisfied clauses. Consequently, there has been a need to define cost-preserving resolution-style proof systems for MaxSAT. In this paper, we present the first MaxSAT resolution proof system specifically defined for regular propositional clausal forms and prove its soundness and completeness. The defined proof system provides an exact approach to solving Regular MaxSAT and Weighted Regular MaxSAT with variable elimination algorithms., This work has been supported by the French Agence Nationale de la Recherche, reference ANR-19-CHIA-0013-01, and grants PID2019-111544GB-C21 and TED2021-129319B-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Advocating CMSA as a Baseline Algorithm for Algorithm Comparison in Combinatorial Optimziation

  • Blum, Christian
Included in the following conference series: International Conference on Information Technology, Adaptive Intelligence: Select Proceedings of InCITe 2024, Volume 1, Conference proceedings., In the field of approximate algorithms for combinatorial optimization, researchers frequently assess their optimization algorithms by comparing them to integer linear programming solvers like CPLEX and Gurobi, whenever feasible. Predictably, the general trend indicates that soft computing techniques such as evolutionary algorithms and tabu search tend to surpass integer linear programming solvers once the difficulty of the considered problem instances exceeds a certain threshold. In this paper, we advocate for adopting (or additionally using) a recent hybrid technique known as CMSA for evaluating newly developed optimization algorithms. CMSA employs an iterative approach, applying integer linear programming solvers to opportunely defined sub-instances of the addressed problem instances. Remarkably, this technique tends to outperform black-box integer linear programming solvers, especially in the context of larger and more challenging problem instances. We substantiate our argument by presenting results related to the bin packing problem with conflicts., The author was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Application of Adapt-CMSA to the Electric Vehicle Routing Problem with Simultaneous Pickup and Deliveries

  • Akbay, Mehmet Anıl
  • Blum, Christian
  • Kalayci, Can Berk
Computer Aided Systems Theory – EUROCAST 2024 19th International Conference, Las Palmas de Gran Canaria, Spain, February 25 – March 1, 2024, Revised Selected Papers, Part I, Conference paper., The Vehicle Routing Problem (VRP) has long been a cornerstone in combinatorial optimization, aiming to optimize the fleet of vehicles delivering goods in a transportation network. With the global shift towards sustainability, Electric Vehicles (EVs) have emerged as a green logistics alternative, leading to the Electric Vehicle Routing Problem with Simultaneous Pickup and Delivery (EVRP-SPD). This problem variant introduces the complexities of EV constraints, such as battery limitations and recharging necessities, coupled with handling delivery and pickup demands simultaneously during a single customer visit. This paper presents the application of the recent hybrid metaheuristic Construct, Merge, Solve & Adapt (CMSA) to the EVRP-SPD. Our self-adaptive version of CMSA, combined with a set covering-based mathematical formulation, offers a promising approach to efficiently tackle larger instances of the problem, aiming to provide high-quality solutions., This paper was supported by grants TED2021-129319B-I00 and PID2019-104156GB-I00 funded by MCIN/AEI/10.13039/501100011033. Moreover, M.A. Akbay and C.B. Kalayci received support from the Technological Research Council of Turkey (TUBITAK) under grant number 119M236. The corresponding author was funded by the Ministry of National Education, Turkey (Scholarship Prog.: YLYS-2019)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

A Short Bibliometric Review of Metaheuristics

  • Akbay, Mehmet Anıl
  • Reixach, Jaume
  • Rodríguez-Corominas, Guillem
  • Chacón Sartori, Camilo
  • Blum, Christian
This paper presents a concise bibliometric review of metaheuristics, a class of high-level, problem-independent algorithmic frameworks designed for heuristic optimization. Since their rise in the late twentieth century, driven largely by advances in computational power, metaheuristics have become increasingly popular in solving complex optimization problems. In this review, we examine the evolution of the metaheuristics literature, highlighting key trends, developments, and the growing impact of this field over time., The research presented in this paper was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/ AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

The Hybrid Metaheuristic CMSA

  • Blum, Christian
  • Reixach, Jaume
In this chapter, we describe the Construct, Merge, Solve & Adapt (CMSA) algorithm, a metaheuristic framework designed to address hard combinatorial optimization problems. CMSA combines the probabilistic construction of solutions within an adaptive, iterative process with solution merging and exact optimization techniques. The algorithm probabilistically constructs solutions through heuristic methods, which are then merged into a reduced subproblem. This subproblem is solved using exact optimization approaches, mostly integer programming. Based on the feedback from this solving phase, the algorithm adapts its construction and merging strategies in subsequent iterations, progressively finding solutions of improving quality over time. CMSA’s hybrid nature allows it to balance between the speed of heuristic construction and the accuracy of exact methods, making it particularly effective for large-scale problems. After a general description of standard CMSA, we outline a recent self-adaptive variant and a variant that uses reinforcement learning to improve the search process. All three algorithm variants are applied to the classical maximum independent set problem. Moreover, an experimental evaluation is provided to show their comparative behavior., The authors were supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Tight Bounds for an Accelerated k-means++ Algorithm

  • Rodríguez-Corominas, Guillem
  • Blesa Aguilera, María Jesús
  • Blum, Christian
21st IFIP WG 12.5 International Conference, AIAI 2025, Limassol, Cyprus, June 26–29, 2025, Proceedings, Part I, Conference proceedings. IFIP (International Federation for Information Processing)., In this paper, we improve a recently introduced accelerated k-means++ algorithm by proposing a dynamic method for calculating bounds during its execution. This approach produces high-quality bounds without requiring a full iteration over the dataset, using the Triangle Inequality and the norm of the points for efficient computation. We propose three evaluation metrics to assess the quality of the calculated bounds and analyze their behavior across a diverse dataset. Results show that this dynamic method outperforms the traditional approach of initializing bounds at the end of the process, before the execution of the -means algorithm., The research presented in this paper was supported by grant 2022 FI_B 00903 funded by the AGAUR; grant PID-2020-112581GB-C21 (MOTION) funded by the AEI; grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033; and project MMT24-IIIA-02 funded by Red.es, Peer reviewed