Menu

orcid.org/0000-0002-1736-3559

		Curriculum Vitae Download PDF
		DBLP entries
		Google Scholar Citations

Research Interests

My research interests are twofold: On one side I am interested in swarm intelligence, which is an artificial intelligence discipline based on the inspiration taken, for example, from the collective behaviour of social insects, flocks of birds, and fish schools. On the other side I am also interested in the hybridization of metaheuristics with more classical artificial intelligence and operations research methods such as, for example, branch and bound techniques and dynamic programming.

I am making use of swarm intelligence concepts both for solving challenging combinatorial optimization problems and for problem solving in distributed enviroments such as adhoc and sensor networks. Well-known swarm intelligence algorithms for combinatorial optimization are ant colony optimization (ACO) and particle swarm optimization (PSO). In distributed environments I have lately made use of the self-organization of natural ant colonies for obtaining synchronized sleep-wake periods, and the self-desynchronization of the calling periods of Japanese tree frogs. Concerning the second research line, I am currently working mainly on two different types of hybridization. First, the hybridization of metaheuristics based on the construction of solutions with concepts from branch and bound. Second, I am working on the development of efficient large neighborhood search algorithms.

Concerning applications, my work has a strong interdisciplinary flavour. In fact, optimization and control tasks arise in many important application areas such as telecommunications, bio-informatics, neuroscience, and robotics. A representative example of recent interdisciplinary work concerns the colboration with the Computer Vision Lab of the EPFL (Lausanne, Switzerland) on the automated reconstruction of dentritic and axonal trees. Concerning the bio-informatics (respectively, bio-medical) field, some of my work has focused on DNA sequencing, the training of neural networks for medical pattern classification, and on the founder sequence reconstruction problem.

Important lines of my work are shortly summarized below.

Hybrid Metaheuristics

Concerning the hybridization of metaheuristics with other techniques for optimization I am mainly working on two different types of hybrids. The first one is known as Beam-ACO. This is an algorithm that results from the combination of ant colony optimization with beam search, a branch and bound derivative. The second hybrid is known as large neighborhood search, which is a special type of local search that uses a complete method for exploring large-scale neighborhoods. The following two papers are recent examples for this line of research.

• A. Roli and S. Benedettini and T. Stuetzle and C. Blum. Large Neighbourhood Search Algorithms for the Founder Sequence Reconstruction Problem. Computers & Operations Research, 39(2):213--224, 2012.

• M. Lopez and C. Blum. Beam-ACO for the travelling salesman problem with time windows. Computers & Operations Research, 37(9):1570--1583, 2010.

Swarm Intelligence

Some of my recent work in swarm intelligence makes use of the self-synchronization observed in natural ant colonies for obtaining a mechanism for self-organized duty-cycling in sensor networks. Another example concerns the use of the calling behaviour of Japanese tree frogs for graph coloring.

• H. Hernandez and C. Blum. Foundations of ANTCYCLE: Self-Synchronized Duty-Cycling in Mobile Sensor Networks. The Computer Journal, 2011. In press.

• H. Hernandez and C. Blum. Distributed Graph Coloring: An Approach Based on the Calling Behavior of Japanese Tree Frogs. Swarm Intelligence, 2012. In press.

Applications

Apart from classical operations research applications, I have recently focused on interesting applications in wireless sensor networks and from the bioinformatics field. An interdisciplinary application from the Neuroscience field is shortly described in the following.

Tree-like structures, such as dendritic, vascular, or bronchial networks, are pervasive in biological systems. Despite of many years of work towards automated delineation techniques, the existing techniques remain fragile and error-prone. In this work, we use 3D optical micrographs of neurons and 2D retinal fundus images to demonstrate the importance of taking global tree structure and geometry into account to improve topological accuracy of the delineations.

The approach that we propose is based on ant colony optimization. It builds a set of candidate trees over many different subsets of points likely to belong to the optimal delineation and then chooses the best one according to a global objective function that combines image evidence with geometric priors.

More information can be otained at http://cvlab.epfl.ch/research/medical/lm/.

• E. Turetgen and G. Gonzalez and C. Blum and P. Fua. Automated Reconstruction of Dendritic and Axonal Trees by Global Optimization with Geometric Priors. Neuroinformatics, 9(2-3):279--302, 2011.

• E. Turetgen and C. Blum and G. Gonzalez and P. Fua. Reconstructing geometrically consistent tree structures from noisy images. In: Proceedings of MICCAI 2010 -- 13th International Conference on Medical Image Computing and Computer-Assisted Intervention., Lecture Notes in Computer Science, Springer, Berlin, Germany, 2010.

Survey Papers

• C. Blum and J. Puchinger and G. Raidl and A. Roli. Hybrid Metaheuristics in Combinatorial Optimization: A Survey. Applied Soft Computing, 11(6):4135--4151, 2011.

• C. Blum. Ant colony optimization: Introduction and recent trends. Physics of Life Reviews, 2(4):353-373, 2005.

• M. Dorigo and C. Blum. Ant colony optimization theory: A survey. Theoretical Computer Science, 344(2-3):243-278, 2005.

• C. Blum and A. Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3):268-308, 2003.

Problem Instances

For the purpose of the experimental evaluation of developed algorithms we frequently generate new sets of problem instances for diverse combinatorial optimization problems. Some of them are provided in the following.

• Group Shop Scheduling (GSS) Problem.: instance sets. These instances were used in this paper, published in the Journal of Mathematical Modelling and Algorithms in 2003.

• K-Cardinality Tree (KCT) Problem.: instance sets. These instances were used in this paper, published in the Computers and Operations Research (COR) in 2005.

• Maximum Edge Disjoint Paths (EDP) Problem.: instance set. These instances were used in this paper, published in the Journal of Mathematical Modelling and Algorithms in 2007.

• Travelling Salesman Problem with Time Windows (TSPTW): Manuel López Ibáñez maintains a nice website providing a lot of information about this problem. Moreover, he offers the problem instances used in our paper for downloading.

• Longest Common Subsequence (LCS) Problem.: instance sets. The format of all files is as follows: the first line contains the number of input strings, and the alphabet size. Then, for each input string that is one line containing, first, the length of the string, and then the string itself. These instances were used in this paper, published in Computers and Operations Research in 2009.

• Assembly Line Worker Assignment and Balancing Problem (ALWABP).: instance set. These instances were used in this paper, published in Computers and Operations Research in 2011.

• Minimum Weight Vertex Cover (MWVC) Problem: graphs. The format of all files is as follows: the first line contains the number of nodes of the graph, the second line contains the node weights, and the remaining lines contain the incidence matrix. Moreover, note that the files containing ds in the file name, are the instances of so-called type II. These instances were used in this paper, published in Applied Soft Computing in 2012.

• Non-Identical Parallel Machine Scheduling Minimizing Weighted Completion Times (SNIM-WCT).: instance set. These instances were used in this paper, published in Annals of Operations Research in 2012.

• Far From Most String Problem (FFMSP).: instance set. These instances were used in this paper, published in the proceedings of EvoCOP in 2014.

• Firefighter (FF) Problem: random graphs, random geometric graphs. The format of all files is the DIMACS graph format. These instances were used in this paper, published in Computers and Operations Research in 2015.

• Minimum Weight Dominating Set (MWDS) Problem: graphs. The format of all files is as follows: the first line contains the number of nodes of the graph. Then, for each node there is one line with its weight. Finally, for each edge there is one line with the two vertices that the edge connects (note that vertex indices range from 0 to n-1). These instances were used in this paper, published in Simulation Modelling Practice and Theory in 2016.

• Minimum Common String Partition (MCSP): each file simply contains the two input strings.

  • Paper 1: instance set. These instances were used in this paper, published in Computers and Operations Research in 2016. The names of the files indicate unambiguously to which instances in the paper they correspond.

  • Paper 2: instance set. These instances were used in this paper, published in International Transcations in Operational Research in 2019.

• Weighted Independent Domination Problem (WIDP): random graphs, random geometric graphs. The format of all files is as follows: the first line contains the number of nodes and the number of edges. Then, there is one line for each node, providing the node weight. Finally, there is one line for each edge, containing the node identifiers and the edge weight. These instances were used in this paper, which is in press at European Journal of Operational Research.

• Repetition-Free Longest Common Subsequence (RFLCS) Problem: file containing Set1 and Set2 instances. The format of all files is as follows: the first line contains the number of input strings (this is 2 in all cases) and the alphabet size. Then, there are two lines for each input string. The first line indicates the length of the corresponding input string, and the second line contains the input string itself in terms of a sequence of integers from {0,...,alphabet_size - 1}. These instances were used in this paper, published in Journal of Heuristics in 2017. The names of the files indicate unambiguously to which instances in the paper they correspond.

• Longest Arc Preserving Common Subsequence (LAPCS) Problem: random instances, real instances. The format of all files is as follows: the first line contains the number of input sequences (which is always 2) and the alphabet size. Then, for each of the input sequences the following information is provided. The first line contains the length of the sequence and the sequence itself. The second line provides the number of arcs (say X). Then there are X lines with the information for each arc: the left position and the right position.

• Most Strings With Few Bad Columns (MSFBC) Problem: all problem instances. The files are organized in directories. At the first level they are split according to alphabet size. At the second level they are separated according to number of input strings and their length. The name of each file indicates, first, the number of input strings, then the length of the input strings, and then the alphabet size. Each file simply contains in the first line the alphabet size, and then one string per line. These instances were used in this paper, published in Soft Computing in 2017.

• Maximizing Sensor Network Lifetime: random graph (RG) instances, and random geometric graph (RGG) instances. In both cases (RG and RGG graphs), the first line of the file contains 5 numbers, of which only the first 2 have a real meaning. The first one is the number of nodes, and the second one the number of edges. Next are n lines (where n is the number of nodes) containing the lifetime values of the n nodes. In the case of the RGG graphs, each line also contains the x and y coordinates of the corresponding node in the [0,1]x[0,1] square. Finally, at each end of each file you find the incidence matrix that shows the existing edges.

Software

Occasionally we provide the code or the executables of our optimization software (programmed in C++ and compiled under Ubuntu 14.04).

• Longest Common Subsequence (LCS) Problem: Hybrid Ant Colony Approach. The archive contains a README file that explains how to compile and use the code. You find the problem instance sets above in the section on problem instances.

• Weighted Independent Domination Problem (WIDP): Population-based Iterated Greedy (PBIG) algorithm, Construct, Solve, Merge and Adapt (CMSA) algorithm (using PBIG for solving subinstances). The way of using these executables is described in README.

• Longest Arc Preserving Common Subsequence (LAPCS) Problem: Ilp-Heur (the heuristic based on ILP reduction), Hyb-Alg (the hybrid algorithm). The way of using these executables is described in README_LAPCS.