230 research outputs found
A tabu search heuristic based on k-diamonds for the weighted feedback vertex set problem
No full textGiven an undirected and vertex weighted graph G = (V,E,w), the Weighted Feedback Vertex Problem (WFVP) consists of finding a subset F ⊆ V of vertices of minimum weight such that each cycle in G contains at least one vertex in F. The WFVP on general graphs is known to be NP-hard and to be polynomially solvable on some special classes of graphs (e.g., interval graphs, co-comparability graphs, diamond graphs). In this paper we introduce an extension of diamond graphs, namely the k-diamond graphs, and give a dynamic programming algorithm to solve WFVP in linear time on this class of graphs. Other than solving an open question, this algorithm allows an efficient exploration of a neighborhood structure that can be defined by using such a class of graphs. We used this neighborhood structure inside our Iterated Tabu Search heuristic. Our extensive experimental show the effectiveness of this heuristic in improving the solution provided by a 2-approximate algorithm for the WFVPon general graphs
A Mathematical Programming Approach for the Maximum Labeled Clique Problem
No full textThis paper addresses a variant of the classical clique problem in which the edges of the graph are labeled. The problem consists of finding a clique as large as possible whose edge set contains at most b ∈ Z+ different labels. Moreover, in case of more feasible cliques of the same maximum size, we look for the one with the minimum number of labels. We study the time complexity of the problem, also in special cases, and we propose a mathematical programming approach for its solution by introducing two different formulations: the basic and the enforced. We experimentally evaluate the performance of the proposed approach on a set of benchmark instances (DIMACS) suitably adapted to the problem
The Rainbow Cycle Cover Problem
No full textWe model and solve the Rainbow Cycle Cover Problem (RCCP). Given a connected and undirected graph G = ( V , E , L ) and a coloring function l that assigns a color to each edge of G from the finite color set L , a cycle whose edges have all different colors is called a rainbow cycle. The RCCP consists of finding the minimum number of disjoint rainbow cycles covering G . The RCCP on general graphs is known to be NP-complete. We model the RCCP as an integer linear program, we derive valid inequalities and we solve it by branch-and-cut. Computational results are reported on randomly generated instances
A reduction heuristic for the all-colors shortest path problem
No full textThe 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
Improving patient’s medical history classification using a feature construction approach based on situation awareness and granular computing
No full textHealthcare decision support systems aid physicians in disease classification by analyzing patients’ medical histories to suggest preliminary diagnoses. As physicians largely base their analysis on anamnesis, integrating this process into an automated recommendation system can expedite decision-making and transition to relevant clinical investigations, thus enhancing efficiency in diagnosing potential pathologies. In this research, an innovative method for feature construction is introduced, drawing on the concepts of Situation Awareness and Granular Computing. The aim of this method is to enhance the performance of out-of-the-box classification algorithms used in machine learning. The approach is specifically tailored to mimic physicians’ cognitive processes when analyzing a patient’s medical history, resulting in the generation of new, information-dense features that can be used for classification tasks. By employing this strategy, a deeper comprehension of the data can be achieved, as well as a more precise categorization of anamneses in relation to possible medical conditions. To authenticate the efficacy of the proposed technique, three major disease categories, namely cardiac, gastrointestinal, and thyroid, were considered. The dataset comprised 1213 medical histories. The experimental results indicate that the study’s six classifiers attained a balanced accuracy exceeding 90%. Among these, the SVM classifier demonstrated the highest balanced accuracy at 93%. Overall, the proposed approach resulted in an average increase of 16 percentage points in balanced accuracy, representing an improvement over the traditional methods commonly employed in machine learning. This approach could be integrated into a clinical decision support system, aiding physicians in accurately identifying necessary investigations and expediting diagnosis
Maximizing lifetime and handling reliability in wireless sensor networks
No full textIn 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
Operations management in distribution networks within a smart city framework
No full textThis article studies a vehicle routing problem with environmental constraints that are motivated by the requirements for sustainable urban transport. The empirical research presents a fleet planning problem that takes into consideration both minimum cost vehicle routes and minimum pollution. The problem is formulated as a mixed integer linear programming model and experimentally validated using data collected from a real situation: a grocery company delivering goods ordered via e-channels to customers spread in the urban and metropolitan area of Genoa smart city. The proposed model is a variant of the vehicle routing problem tailored to include environmental issues and street limitations. Its novelty regards also the use of real data instances provided by the B2C grocery company. Managerial implications are the choice of both the routes and the number and type of vehicles. Results show that commercial distribution strategies achieve better results in term of both business and environmental performance, provided the smart mobility goals and constraints are included into the distribution model from the beginning
A Dual Ascent Approach to the Bounded-Degree Spanning Tree Problem
No full textGiven a connected graph G a vertex is said to be of the branch type if its
degree is greater than 2. We consider the problem of nding a spanning
tree of G which minimizes the number of branch vertices. Such a problem
has been proved to be NP-complete, and some efcient heuristics
to solve it have been proposed in the literature. In the paper we present
a new heuristic algorithm based on solving the Lagrangean dual of the
original mixed integer programming problem by means of a dual ascent
procedure requiring update of one multiplier at a time
Exact and Heuristic Methods to Maximize Network Lifetime in Wireless Sensor Networks with Adjustable Sensing Ranges
No full textWireless sensor networks involve many dierent real-world contexts, such as monitoring and control tasks for traffic, surveillance, military and environmental applications, among others. Usually, these applications consider the use of a large number of low-cost sensing devices to monitor the activities
occurring in a certain set of target locations. We want to individuate a set of covers (that is, subsets of sensors that can cover the whole set of targets) and appropriate activation times for each of them in order to maximize the total amount of time in which the monitoring activity can be performed (network
lifetime), under the constraint given by the limited power of the battery contained in each sensor. A variant of this problem considers that each sensor can be activated in a certain number of alternative power levels, which determine dierent sensing ranges and power consumptions. We present some heuristic
approaches and an exact approach based on the Column Generation technique. An extensive experimental
phase proves the advantage in terms of solution quality of using adjustable sensing ranges with respect to the classical single range scheme
A branch‐and‐bound algorithm for the double travelling salesman problem with two stacks
No full textThis article studies the double traveling salesman problem with two stacks. A number of requests have to be
served where each request consists in the pickup and
delivery of an item. All the pickup operations have to be
performed before any delivery can take place. A single
vehicle is available that starts from a depot, performs all
the pickup operations and returns to the depot. Then, it
performs all the delivery operations and returns to the
depot. The items are loaded in two stacks, each served
independently from the other with a last-in-first-out policy. The objective is the minimization of the total cost
of the pickup and delivery tours. We propose a branchand-bound approach to solve the problem. The algorithm
uses properties of the problem both to tighten the lower
bounds and to avoid the exploration of redundant subtrees. Computational results performed on benchmark
instances reveal that the algorithm outperforms the other
exact approaches for this problem
- …
