CERULLI R.

In this paper we take into account three different spanning tree problems with degree-dependent objective functions. The main application of these problems is in the field of optical network design. In particular, we propose the classical Minimum Leaves Spanning Tree problem as a relevant problem in this field and show its relations with the...

We address an important problem in the context of traffic management and control related to the optimum location of vehicle-ID sensors on the links of a network to derive route flow volumes. We consider both the full observability version of the problem, where one seeks for the minimum number of sensors (or minimum cost) such that all the route...

The genetic algorithm (GA) is a quite efficient paradigm to solve several optimization problems. It is substantially a search technique that uses an ever-changing neighborhood structure related to a population which evolves according to a number of genetic operators. In the GA framework many techniques have been devised to escape from a local...

Given an undirected and vertex weighted graph G = (V,E,w), the Weighted Feedback Vertex Set Problem consists of finding the subset F ⊆ V of vertices, with minimum weight, whose removal results in an acyclic graph. Finding the minimum feedback vertex set in a graph is an important combinatorial problem that has a variety of real applications. In...

This paper concerns the problem to place N non overlapping circles in a circular container with minimum radius. This is a well known and widely studied problem with applications in manufacturing and logistics and, in particular, to problems related to cutting and packing. In this paper we propose an algorithm that by applying a strength along a...

In this paper, we introduce carousel greedy, an enhanced greedy algorithm which seeks to overcome the traditional weaknesses of greedy approaches. We have applied carousel greedy to a variety of well-known problems in combinatorial optimization such as the minimum label spanning tree problem, the minimum vertex cover problem, the maximum...

The close-enough arc routing problem is a generalization of the classic arc routing problem and it has many interesting real-life applications. In this paper, we propose some techniques to reduce the size of the input graph and a new effective mixed integer programming formulation for the problem. Our experiments on directed graphs show the...

Given an undirected and edge-colored graph G, a rainbow component of G is a subgraph of G having all the edges with different colors. The Rainbow Spanning Forest Problem consists of finding a spanning forest of G with the minimum number of rainbow components. The problem is known to be NP-hard on general graphs and on trees. In this paper, we...

This paper addresses the close-enough traveling salesman problem, a variant of the Euclidean traveling salesman problem, in which the traveler visits a node if it passes through the neighborhood set of that node. We apply an effective strategy to discretize the neighborhoods of the nodes and the carousel greedy algorithm to appropriately select...

Given a graph G = (V, E, L) and a coloring function l : E -> L, that assigns a color to each edge of G from a finite color set L, the rainbow spanning forest problem (RSFP) consists of finding a rainbow spanning forest of G such that the number of components is minimum. A spanning forest is rainbow if all its components (trees) are rainbow. A...

The problem of optimally locating sensors on a traffic network to monitor flows has been an object of growing interest in the past few years, due to its relevance in the field of traffic management and control. Sensors are often located in a network in order to observe and record traffic flows on arcs and/or nodes. Given traffic levels on arcs...

This paper addresses a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood set of that node. The problem is known as the close-enough traveling salesman problem. We introduce a new effective discretization scheme that allows us to compute both a lower and an upper bound...

This paper studies the close-enough traveling salesman problem, a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood of that node. We introduce an improved version of the adaptive internal discretization scheme, recently proposed in the literature, and a heuristic that...

We consider a distribution problem in a supply chain consisting of multiple plants, multiple regional warehouses, and multiple customers. We focus on the problem of selecting a given number of warehouses among a set of candidate ones, assigning each customer to one or more of the selected warehouses while minimizing costs. We present a mixed...

There are several examples of dual propulsion vehicles: hybrid cars, bi-fuel vehicles, electric bikes. Compute a path from a starting point to a destination for these typologies of vehicles requires evaluation of many alternatives. In this paper we develop a mathematical model, able to compute paths for dual propulsion vehicles, that takes in...