Search

Abstract 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 $$\textsc {Learn}\_\textsc {Cmsa}$$ L E A R N _ C M S A 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. $$\textsc {Learn}\_\textsc {Cmsa}$$ L E A R N _ C M S A 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, $$\textsc {Learn}\_\textsc {Cmsa}$$ L E A R N _ C M S A achieves superior performance when compared to current state-of-the-art solvers.

The true extent of plastic particle pollution is largely unknown, particularly for particles

Abstract Recently, a new negative learning variant of ant colony optimization (ACO) has been used to successfully tackle a range of combinatorial optimization problems. For providing stronger evidence of the general applicability of negative learning ACO, we investigate how it can be adapted to solve the Maximum Satisfiability problem (MaxSAT). The structure of MaxSAT is different from the problems considered to date and there exists only a few ACO approaches for MaxSAT. In this paper, we describe three negative learning ACO variants. They differ in the way in which sub-instances are solved at each algorithm iteration to provide negative feedback to the main ACO algorithm. In addition to using IBM ILOG CPLEX, two of these variants use existing MaxSAT solvers for this purpose. The experimental results show that the proposed negative learning ACO variants significantly outperform the baseline ACO as well as IBM ILOG CPLEX and the two MaxSAT solvers. This result is of special interest because it shows that negative learning ACO can be used to improve over the results of existing solvers by internally using them to solve smaller sub-instances.

Abstract Construct, merge, solve and adapt (CMSA) is a recently developed, generic algorithm for combinatorial optimisation. Even though the usefulness of the algorithm has been demonstrated by applications to a range of combinatorial optimisation problems, in some applications, it was observed that the algorithm can be sensitive to parameter settings. In this work, we propose a self-adaptive variant of CMSA, called Adapt-CMSA, with the aim of reducing the parameter sensitivity of the original version of CMSA. The advantages of this new CMSA variant are demonstrated in the context of the application to the so-called minimum positive influence dominating set problem. It is shown that, in contrast to CMSA, Adapt-CMSA does not require a computation time intensive parameter tuning process for subsets of the considered set of problem instances. In fact, after tuning Adapt-CMSA only once for the whole set of benchmark instances, the algorithm already obtains state-of-the-art results. Nevertheless, note that the main objective of this paper is not the tackled problem but the improvement of CMSA.

Objective To analyse the clinical profile of SARS-CoV-2 breakthrough infections in at least double-vaccinated patients with inflammatory rheumatic diseases (IRDs).Methods Data from the physician-reported German COVID-19-IRD registry collected between February 2021 and July 2022 were analysed. SARS-CoV-2 cases were stratified according to patients’ vaccination status as being not vaccinated, double-vaccinated or triple-vaccinated prior to SARS-CoV-2 infection and descriptively compared. Independent associations between demographic and disease features and outcome of breakthrough infections were estimated by multivariable logistic regression.Results In total, 2314 cases were included in the analysis (unvaccinated n=923, double-vaccinated n=551, triple-vaccinated n=803, quadruple-vaccinated n=37). SARS-CoV-2 infections occurred after a median of 151 (range 14–347) days in patients being double-vaccinated, and after 88 (range 14–270) days in those with a third vaccination. Hospitalisation was required in 15% of unvaccinated, 8% of double-vaccinated and 3% of triple-vaccinated/quadruple-vaccinated patients (p

Due to a minor programming mistake, the authors had to fix the bug and repeat all computational experiments reported in [...]

Finding dominating sets in graphs is very important in the context of numerous real-world applications, especially in the area of wireless sensor networks. This is because network lifetime in wireless sensor networks can be prolonged by assigning sensors to disjoint dominating node sets. The nodes of these sets are then used by a sleep–wake cycling mechanism in a sequential way; that is, at any moment in time, only the nodes from exactly one of these sets are switched on while the others are switched off. This paper presents a population-based iterated greedy algorithm for solving a weighted version of the maximum disjoint dominating sets problem for energy conservation purposes in wireless sensor networks. Our approach is compared to the ILP solver, CPLEX, which is an existing local search technique, and to our earlier greedy algorithm. This is performed through its application to 640 random graphs from the literature and to 300 newly generated random geometric graphs. The results show that our algorithm significantly outperforms the competitors.

Increasing environmental concerns and legal regulations have led to the development of sustainable technologies and systems in logistics, as in many fields. The adoption of multi-echelon distribution networks and the use of environmentally friendly vehicles in freight distribution have become major concepts for reducing the negative impact of urban transportation activities. In this line, the present paper proposes a two-echelon electric vehicle routing problem. In the first echelon of the distribution network, products are transported from central warehouses to satellites located in the surroundings of cities. This is achieved by means of large conventional trucks. Subsequently, relatively smaller-sized electric vehicles distribute these products from the satellites to demand points/customers located in the cities. The proposed problem also takes into account the limited driving range of electric vehicles that need to be recharged at charging stations when necessary. In addition, the proposed problem considers time window constraints for the delivery of products to customers. A mixed-integer linear programming formulation is developed and small-sized instances are solved using CPLEX. Furthermore, we propose a constructive heuristic based on a modified Clarke and Wright savings heuristic. The solutions of this heuristic serve as initial solutions for a variable neighborhood search metaheuristic. The numerical results show that the variable neighborhood search matches CPLEX in the context of small problems. Moreover, it consistently outperforms CPLEX with the growing size and difficulty of problem instances.

Supramolecular protein complexes are the corner stone of biological processes; they are essential for many biological functions. Unraveling the interactions responsible for the (dis)assembly of these complexes is required to understand nature and to exploit such systems in future applications. Virus capsids are well-defined assemblies of hundreds of proteins and form the outer shell of non-enveloped viruses. Due to their potential as a drug carriers or nano-reactors and the need for virus inactivation strategies, assessing the intactness of virus capsids is of great interest. Current methods to evaluate the (dis)assembly of these protein assemblies are experimentally demanding in terms of instrumentation, expertise and time. Here we investigate a new strategy to monitor the disassembly of fluorescently labeled virus capsids. To monitor surfactant-induced capsid disassembly, we exploit the complex photophysical interplay between multiple fluorophores conjugated to capsid proteins. The disassembly of the capsid changes the photophysical interactions between the fluorophores, and this can be spectrally monitored. The presented data show that this low complexity method can be used to study and monitor the disassembly of supramolecular protein complexes like virus capsids. However, the range of labeling densities that is suitable for this assay is surprisingly narrow.

The longest common subsequence (LCS) problem is a prominent NP–hard optimization problem where, given an arbitrary set of input strings, the aim is to find a longest subsequence, which is common to all input strings. This problem has a variety of applications in bioinformatics, molecular biology and file plagiarism checking, among others. All previous approaches from the literature are dedicated to solving LCS instances sampled from uniform or near-to-uniform probability distributions of letters in the input strings. In this paper, we introduce an approach that is able to effectively deal with more general cases, where the occurrence of letters in the input strings follows a non-uniform distribution such as a multinomial distribution. The proposed approach makes use of a time-restricted beam search, guided by a novel heuristic named Gmpsum. This heuristic combines two complementary scoring functions in the form of a convex combination. Furthermore, apart from the close-to-uniform benchmark sets from the related literature, we introduce three new benchmark sets that differ in terms of their statistical properties. One of these sets concerns a case study in the context of text analysis. We provide a comprehensive empirical evaluation in two distinctive settings: (1) short-time execution with fixed beam size in order to evaluate the guidance abilities of the compared search heuristics; and (2) long-time executions with fixed target duration times in order to obtain high-quality solutions. In both settings, the newly proposed approach performs comparably to state-of-the-art techniques in the context of close-to-uniform instances and outperforms state-of-the-art approaches for non-uniform instances.

Dominating sets are among the most well-studied concepts in graph theory, with many real-world applications especially in the area of wireless sensor networks. One way to increase network lifetime in wireless sensor networks consists of assigning sensors to disjoint dominating node sets, which are then sequentially used by a sleep–wake cycling mechanism. This paper presents a greedy heuristic for solving a weighted version of the maximum disjoint dominating sets problem for energy conservation purposes in wireless sensor networks. Moreover, an integer linear programming model is presented. Experimental results based on a large set of 640 problem instances show, first, that the integer linear programming model is only useful for small problem instances. Moreover, they show that our algorithm outperforms recent local search algorithms from the literature with respect to both solution quality and computation time.

Ant colony optimization is a metaheuristic that is mainly used for solving hard combinatorial optimization problems. The distinctive feature of ant colony optimization is a learning mechanism that is based on learning from positive examples. This is also the case in other learning-based metaheuristics such as evolutionary algorithms and particle swarm optimization. Examples from nature, however, indicate that negative learning—in addition to positive learning—can beneficially be used for certain purposes. Several research papers have explored this topic over the last decades in the context of ant colony optimization, mostly with limited success. In this work we present and study an alternative mechanism making use of mathematical programming for the incorporation of negative learning in ant colony optimization. Moreover, we compare our proposal to some well-known existing negative learning approaches from the related literature. Our study considers two classical combinatorial optimization problems: the minimum dominating set problem and the multi dimensional knapsack problem. In both cases we are able to show that our approach significantly improves over standard ant colony optimization and over the competing negative learning mechanisms from the literature.

This paper presents a performance comparison of greedy heuristics for a recent variant of the dominating set problem known as the minimum positive influence dominating set (MPIDS) problem. This APX-hard combinatorial optimization problem has applications in social networks. Its aim is to identify a small subset of key influential individuals in order to facilitate the spread of positive influence in the whole network. In this paper, we focus on the development of a fast and effective greedy heuristic for the MPIDS problem, because greedy heuristics are an essential component of more sophisticated metaheuristics. Thus, the development of well-working greedy heuristics supports the development of efficient metaheuristics. Extensive experiments conducted on a wide range of social networks and complex networks confirm the overall superiority of our greedy algorithm over its competitors, especially when the problem size becomes large. Moreover, we compare our algorithm with the integer linear programming solver CPLEX. While the performance of CPLEX is very strong for small and medium-sized networks, it reaches its limits when being applied to the largest networks. However, even in the context of small and medium-sized networks, our greedy algorithm is only 2.53% worse than CPLEX.

The minimum capacitated dominating set problem is an NP-hard variant of the well-known minimum dominating set problem in undirected graphs. This problem finds applications in the context of clustering and routing in wireless networks. Two algorithms are presented in this work. The first one is an extended version of construct, merge, solve and adapt, while the main contribution is a hybrid between a biased random key genetic algorithm and an exact approach which we labeled Barrakuda. Both algorithms are evaluated on a large set of benchmark instances from the literature. In addition, they are tested on a new, more challenging benchmark set of larger problem instances. In the context of the problem instances from the literature, the performance of our algorithms is very similar. Moreover, both algorithms clearly outperform the best approach from the literature. In contrast, Barrakuda is clearly the best-performing algorithm for the new, more challenging problem instances.

Matheuristics have been gaining in popularity for solving combinatorial optimisation problems in recent years. This new class of hybrid method combines elements of both mathematical programming for intensification and metaheuristic searches for diversification. A recent approach in this direction has been to build a neighbourhood for integer programs by merging information from several heuristic solutions, namely construct, solve, merge and adapt (CMSA). In this study, we investigate this method alongside a closely related novel approach—merge search (MS). Both methods rely on a population of solutions, and for the purposes of this study, we examine two options: (a) a constructive heuristic and (b) ant colony optimisation (ACO); that is, a method based on learning. These methods are also implemented in a parallel framework using multi-core shared memory, which leads to improving the overall efficiency. Using a resource constrained job scheduling problem as a test case, different aspects of the algorithms are investigated. We find that both methods, using ACO, are competitive with current state-of-the-art methods, outperforming them for a range of problems. Regarding MS and CMSA, the former seems more effective on medium-sized problems, whereas the latter performs better on large problems.

In this paper, we explore the potential of mobile robots with simulation-based internal models for safety in highly dynamic environments. We propose a robot with a simulation of itself, other dynamic actors and its environment, inside itself. Operating in real time, this simulation-based internal model is able to look ahead and predict the consequences of both the robot’s own actions and those of the other dynamic actors in its vicinity. Hence, the robot continuously modifies its own actions in order to actively maintain its own safety while also achieving its goal. Inspired by the problem of how mobile robots could move quickly and safely through crowds of moving humans, we present experimental results which compare the performance of our internal simulation-based controller with a purely reactive approach as a proof-of-concept study for the practical use of simulation-based internal models.

In recent years, philosophers, political scientists and sociologists have witnessed a renaissance of the concept of the common good in political discourse: political agents such as parties, civic networks and courts increasingly refer to this concept to justify their actions. This development gives rise to the question whether normative political theory can provide a sensible definition of the common good which is compatible with pluralistic democratic society and which allows the identification of a specific range of well justified policies. The most influential account in this field is the theory of proceduralism which holds that the common good consists, by necessity, in the output of a political system whose procedures grant each citizen an equal say in collective decision-making. This account derives its initial plausibility from acknowledging citizens as agents who autonomously shape the welfare of their community on the basis of their subjective interests. However, it falls short of explaining how democratic decision-making good could possibly authorize actions that are detrimental to the common good. This problem is solved by a modification of the proceduralist paradigm that complements procedural criteria with objective and substantive standards that serve as limiting values for admissible policy outputs.

We report a single molecule detection scheme to investigate excitation spectra of single emitters at room temperature. We demonstrate the potential of single emitter photoluminescence excitation spectroscopy by recording excitation spectra of single CdSe nanocrystals over a wide spectral range of 100 nm. The spectra exhibit emission intermittency, characteristic of single emitters. We observe large variations in the spectra close to the band edge, which represent the individual heterogeneity of the observed quantum dots. We also find specific excitation wavelengths for which the single quantum dots analyzed show an increased propensity for a transition to a long-lived dark state. We expect that the additional capability of recording excitation spectra at room temperature from single emitters will enable insights into the photophysics of emitters that so far have remained inaccessible.