Abstract This work addresses the Knapsack Problem with Forfeit Sets, a recently introduced variant of the 0/1 Knapsack Problem considering subsets of items associated with contrasting choices. Some penalty costs need to be paid whenever the number of items in the solution belonging to a forfeit set exceeds a predefined allowance threshold. We propose an effective metaheuristic to solve the problem, based on the Biased Random-Key Genetic Algorithm paradigm. An appropriately designed decoder function assigns a feasible solution to each chromosome, and improves it using some additional heuristic procedures. We show experimentally that the algorithm outperforms significantly a previously introduced metaheuristic for the problem.

MOTIVATION: Binary (or Boolean) matrices provide a common effective data representation adopted in several domains of computational biology, especially for investigating cancer and other human diseases. For instance, they are used to summarize genetic aberrations-copy number alterations or mutations-observed in cancer patient cohorts, effectively highlighting combinatorial relations among them. One of these is the tendency for two or more genes not to be co-mutated in the same sample or patient, i.e. a mutual-exclusivity trend. Exploiting this principle has allowed identifying new cancer driver protein-interaction networks and has been proposed to design effective combinatorial anti-cancer therapies rationally. Several tools exist to identify and statistically assess mutual-exclusive cancer-driver genomic events. However, these tools need to be equipped with robust/efficient methods to sort rows and columns of a binary matrix to visually highlight possible mutual-exclusivity trends. RESULTS: Here, we formalize the mutual-exclusivity-sorting problem and present MutExMatSorting: an R package implementing a computationally efficient algorithm able to sort rows and columns of a binary matrix to highlight mutual-exclusivity patterns. Particularly, our algorithm minimizes the extent of collective vertical overlap between consecutive non-zero entries across rows while maximizing the number of adjacent non-zero entries in the same row. Here, we demonstrate that existing tools for mutual-exclusivity analysis are suboptimal according to these criteria and are outperformed by MutExMatSorting. AVAILABILITY AND IMPLEMENTATION: https://github.com/AleVin1995/MutExMatSorting. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Online social networks are nowadays one of the most effective and widespread tools used to share information. In addition to being employed by individuals for communicating with friends and acquaintances, and by brands for marketing and customer service purposes, they constitute a primary source of daily news for a significant number of users. Unfortunately, besides legit news, social networks also allow to effectively spread inaccurate or even entirely fabricated ones. Also due to sensationalist claims, misinformation can spread from the original sources to a large number of users in a very short time, with negative consequences that, in extreme cases, can even put at risk public safety or health. In this work we discuss and propose methods to limit the spread of misinformation over online social networks. The issue is split in two separate sub-problems. We first aim to identify the most probable sources of the misinformation among the subset of users that have been reached by it. In the second step, assuming to know the misinformation sources, we want to locate a minimum number of monitors (that is, entities able to identify and block false information) in the network in order to prevent that the misinformation campaign reaches some “critical” nodes while maintaining low the number of nodes exposed to the infection. For each of the two issues, we provide both heuristics and mixed integer programming formulations. To verify the quality and efficiency of our suggested solutions, we conduct experiments on several real-world networks. The results of this extensive experimental phase validate our heuristics as effective tools to contrast the spread of misinformation in online social networks. Regarding the source identification step, our approach showed success rates above 80% in most of the considered settings, and above 60% in almost all of them. With respect to the second issue, our heuristic proved to be able to obtain solutions that exceeded (in terms of number of required monitors) the ones obtained through our MILP-based approach of more than 20% in only few test scenarios. Our heuristics for both problems also proved to outperform significantly some previously proposed algorithms.

Abstract In this work we introduce and study the strong generalized minimum label spanning tree (GMLST), a novel optimization problem defined on edge‐labeled graphs. Given a label set associated to each edge of the input graph, the aim is to look for the spanning tree using the minimum number of labels. Differently from the previously introduced GMLST problem, including a given edge in the solution means that all its labels are used. We present a mathematical formulation, as well as three heuristic approaches to solve the problem. Computational results compare the performances of the proposed algorithms.

In this article, we face the problem of ensuring reliability of a wireless sensor network which is monitoring a given set of points of interest while maximizing its lifetime (i.e., the amount of time over which the monitoring activity can be performed). The two objectives are contrasting. Indeed, the traditional approach to achieve reliability involves providing redundant coverage, which, however, drastically reduces the network lifetime. We propose an alternative strategy where sensors adapt their sensing radii in response to failures to restore feasibility only when needed. We provide Column Generation exact algorithms for both the traditional approach and our variant, as well as a heuristic procedure for the coverage restoration phase. The advantages of our approach are shown by means of computational tests on a set of instances and failure simulations. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(4), 321–338 2014