In this work we propose a bi-objective variant of the well-known 0/1 Knapsack Problem, that finds application in cases in which some item pairs may be seen as mutually conflicting. Previous variants considered in this scenario proposed to either avoid all conflicts, or to deal with them by considering the payment of appropriate penalty costs. We propose a different approach where the maximization of the profit and the minimization of the accepted conflicts are considered two different objective functions. We aim at identifying all Pareto-optimal solutions, so that a decision maker may choose a posteriori the optimal trade-off. We propose an exact resolution method based on the epsilon-constraint approach. Computational results on a wide set of instances show that our approach can be used in practice to identify and analyze their Pareto front.

In this work, we propose a novel Biased Random-Key Genetic Algorithm (BRKGA) to solve the Maximum Flow with Minimum Number of Labels (MF-ML) problem, a challenging NP-Complete variant of the classical Maximum Flow problem defined on graphs in which arcs have both capacities and labels assigned. Labels give a qualitative characterization of each connection, in contexts where a solution that is as homogeneous as possible is sought. The MF-ML problem aims to maximize the flow from a source to a sink on a capacitated network while minimizing the number of distinct arc labels used, a modeling framework with applications such as water purification in distribution systems. Our proposed algorithm encodes solutions as random-key vectors, which are decoded into feasible solutions. The BRKGA demonstrates superior performance when compared to a Skewed Variable Neighborhood Search (VNS) approach previously proposed to solve MF-ML. In particular, on the largest considered graphs, BRKGA-MFML outperformed VNS in 55 out of 81 scenarios, with an average improvement per scenario that reaches 7.18%.

The ability of network users to influence other users’ behavior has deep implications for fields such as marketing, epidemiology, misinformation control, and cybersecurity. While traditional models have extensively studied the cascading effects of influence without considering the speed of propagation, this work highlights methodologies that account for this aspect, reviewing the recent advancements in the study of rapid influence (i.e., influence propagation limited to a fixed number of hops or within a minimal time frame from the initial seed set). We provide a comprehensive review of the different variants of this problem studied in the literature, discussing both the theoretical aspects and practical implications, as well as the proposed solution approaches.

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.

This work introduces a novel extension of the 0/1 Knapsack Problem in which we consider the existence of so-called forfeit sets. A forfeit set is a subset of items of arbitrary cardinality, such that including a number of its elements that exceeds a predefined allowance threshold implies some penalty costs to be paid in the objective function value. A global upper bound on these allowance violations is also considered. We show that the problem generalizes both the Knapsack Problem with conflicts among item pairs and the Knapsack Problem with forfeit pairs, that have been previously introduced in the literature. We present a polynomial subcase by proving the integrality of its LP relaxation polytope and, we introduce three heuristic approaches, namely a constructive greedy, an algorithm based on the recently introduced Carousel Greedy paradigm and a hybrid Memetic/Carousel Greedy algorithm. Finally, we validate the performances for the proposed algorithms on a set of benchmark instances that consider both random and correlated data.

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 patientcohorts, 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 effectivecombinatorial anti-cancer therapies rationally. Several tools exist to identify and statistically assess mutualexclusive 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.

In this paper, we present a novel hybrid metaheuristic for the Knapsack Problem with Forfeits (KPF). KPF is a recently introduced generalization of the Knapsack Problem. In this variant, a penalty cost incurs whenever both items composing a so-called forfeit pair belong to the solution. Our proposed algorithm, called GA-CG Forfeits, combines the strengths of the Genetic and Carousel Greedy paradigms. In this work, we define the algorithm and compare it with two previously proposed heuristics on a set of benchmark instances. In these tests, GA-CG Forfeits provided significantly better solutions than the other two algorithms on all instances.

The maximum network lifetime is a well known and studied optimization problem. The aim is to appropriately schedule the activation intervals of the individual sensing devices composing a wireless sensor network used for monitoring purposes, in order to keep the network operational for the longest period of time (network lifetime). In this work, we extend this problem by taking into account the issue of charging the sensor batteries. More specifically, it has to be decided how much charge should be provided to each sensor, given the existence of a charging device with limited energy availability. An exact column generation algorithm embedding a genetic algorithm for the subproblem is proposed. Computational results reveal that by appropriately choosing the charge levels, remarkable network lifetime improvements can be obtained, in particular when the available energy is scarce.

In this paper, we show a branch-and-cut approach to solve the minimum spanning tree problem with conflicting edge pairs. This is a NP-hard variant of the classical minimum spanning tree problem, in which there are mutually exclusive edges. We introduce a new set of valid inequalities for the problem, based on the properties of its feasible solutions, and we develop a branch-and-cut algorithm based on them. Computational tests are performed both on benchmark instances coming from the literature and on some newly proposed ones. Results show that our approach outperforms a previous branch-and-cut algorithm proposed for the same problem.

The All-Colors Shortest Path (ACSP) is a recently introduced NP-Hard optimization problem, in which a color is assigned to each vertex of an edge weighted graph, and the aim is to find the shortest path spanning all colors. The solution path can be not simple, that is it is possible to visit multiple times the same vertices if it is a convenient choice. The starting vertex can be constrained (ACSP) or not (ACSP-UE). We propose a reduction heuristic based on the transformation of any ACSP-UE instance into an Equality Generalized Traveling Salesman Problem one. Computational results show the algorithm to outperform the best previously known one.

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.

In this paper we introduce and study the Knapsack Problem with Forfeits. With respect to the classical definition of the problem, we are given a collection of pairs of items, such that the inclusion of both in the solution involves a reduction of the profit. We propose a mathematical formulation and two heuristic algorithms for the problem. Computational results validate the effectiveness of our approaches.

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.

This book constitutes the refereed proceedings of the 9th International Conference on Computational Logistics, ICCL 2018, held in Vietri sul Mare, Italy, in October 2018. The 32 full papers presented were carefully reviewed and selected from 71 submissions. They are organized in topical sections as follows: maritime shipping and routing, container handling and container terminals, vehicle routing and multi-modal transportation, network design and scheduling, logistics oriented combinatorial optimization.

Given an undirected weighted graph, in which each vertex is assigned to a color and one of them is identified as source, in the all-colors shortest path problem we look for a minimum cost shortest path that starts from the source and spans all different colors. The problem is known to be NP-Hard and hard to approximate. In this work we propose a variant of the problem in which the source is unspecified and show the two problems to be computationally equivalent. Furthermore, we propose a mathematical formulation, a compact representation for feasible solutions and a VNS metaheuristic that is based on it. Computational results show the effectiveness of the proposed approach for the two problems.

We consider a scenario in which it is necessary to monitor a geographical region of interest through a network of sensing devices. The region is divided into subregions of regular sizes (zones), such that if a sensor can even partially monitor the zone, the detected information can be considered representative of the entire subregion. The aim is to schedule the sensor active and idle states in order to maximize the lifetime of the network. We take into account two main types of scenarios. In the first one, the whole region is partitioned into zones. In the second one, a predefined number of possibly overlapping zones are randomly placed and oriented inside the region. We discuss how to transform any problem instance into a target coverage one, and solve the problem through a highly competitive column generation-based method.

In this work, we face a variant of the capacitated lot sizing problem. This is a classical problem addressing the issue of aggregating lot sizes for a finite number of discrete periodic demands that need to be satisfied, thus setting up production resources and eventually creating inventories, while minimizing the overall cost. In the proposed variant we take into account lifetime constraints, which model products with maximum fixed shelflives due to several possible reasons, including regulations or technical obsolescence. We propose four formulations, derived from the literature on the classical version of the problem and adapted to the proposed variant. An extensive experimental phase on two datasets from the literature is used to test and compare the performance of the proposed formulations.

We face the problem of scheduling optimally the activities in a wireless sensor network in order to ensure that, in each instant of time, the activated sensors can monitor all points of interest (targets) and route the collected information to a processing facility. Each sensor is allocated to a role, depending on whether it is actually used to monitor the targets, to forward information or kept idle, leading to different battery consumption ratios. We propose a column generation algorithm that embeds a highly efficient genetic metaheuristic for the subproblem. Moreover, to optimally solve the subproblem, we introduce a new formulation with fewer integer variables than a previous one proposed in the literature. Finally, we propose a stopping criterion to interrupt the optimal resolution of the subproblem as soon as a favorable solution is found. The results of our computational tests show that our algorithm consistently outperforms previous approaches in the literature, and also improves the best results known to date on some benchmark instances.

The aim of the Connected Maximum Lifetime Problem is to define a schedule for the activation intervals of the sensors deployed inside a region of interest, such that at all times the activated sensors can monitor a set of interesting target locations and route the collected information to a central base station, while maximizing the total amount of time over which the sensor network can be operational. Complete or partial coverage of the targets are taken into account. To optimally solve the problem, we propose a column generation approach which makes use of an appropriately designed genetic algorithm to overcome the difficulty of solving the subproblem to optimality in each iteration. Moreover, we also devise a heuristic by stopping the column generation procedure as soon as the columns found by the genetic algorithm do not improve the incumbent solution. Comparisons with previous approaches proposed in the literature show our algorithms to be highly competitive, both in terms of solution quality and computational time.

We aim to maximize the operational time of a network of sensors, which are used to monitor a predefined set of target locations. The classical approach proposed in the literature consists in individuating subsets of sensors (covers) that can individually monitor the targets, and in assigning appropriate activation times to each cover. Indeed, since sensors may belong to multiple covers, it is important to make sure that their overall battery capacities are not violated. We consider additional constraints that prohibit certain sensors to appear in the same cover, since they would interfere with each other. We propose a Column Generation approach, in which the pricing subproblem is solved either exactly or heuristically by means of a recently introduced technique to enhance basic greedy algorithms, known as Carousel Greedy. Our experiments show the effectiveness of this approach.