Gravity-based heuristic for set covering problems and its application in fault diagnosis

A novel algorithm named randomized binary gravita- tional search （RBGS） algorithm is proposed for the set covering problem （SCP）. It differs from previous SCP approaches because it does not work directly on the SCP matrix. In the proposed algo- rithm, the solution of SCP is viewed as multi-dimension position of objects in the binary search space. All objects in the space attract each other by the gravity force, and this force causes a global movement of all objects towards the objects with heavier masses which correspond to good solutions. Computation results show that the proposed algorithm is very competitive. In addition, the proposed aigodthm is extended for SCP to solve the fault diagno- sis problem in graph-based systems.

Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

Currently,the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems.In this sense,metaheuristics have been a common trend in the field in order to design approaches to solve them successfully.Thus,a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments.Following the No Free Lunch theorem,we are interested in testing the performance of the Fruit Fly Algorithm,this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces,based on the foraging behavior of the fruit fly,which usually has much better sensory perception of smell and vision than any other species.On the other hand,the Set Coverage Problem is a well-known NP-hard problem with many practical applications,including production line balancing,utility installation,and crew scheduling in railroad and mass transit companies.In this paper,we propose different binarization methods for the Fruit Fly Algorithm,using Sshaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space.We are motivated with this approach,because in this way we can deliver to future researchers interested in this area,a way to be able to work with continuous metaheuristics in binary domains.This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost.

SET COVERING-BASED TOPSIS METHOD FOR SLOVING SUP-T EQUATION CONSTRAINED MULTI-OBJECTIVE OPTIMIZATION PROBLEMS

This paper considers solving a multi-objective optimization problem with sup-T equation constraints A set covering-based technique for order of preference by similarity to the ideal solution is proposed for solving such a problem. It is shown that a compromise solution of the sup-T equation constrained multi-objective optimization problem can be obtained by ＂solving an associated set covering problem. A surrogate heuristic is then applied to solve the resulting optimization problem. Numerical experiments on solving randomly generated multi-objective optimization problems with sup-T equation constraints are included. Our computational results confirm the efficiency of the proposed method and show its potential for solving large scale sup-T equation constrained multi-objective optimization problems.

Input Data Dependency of a Genetic Algorithm to Solve the Set Covering Problem

A genetic algorithm to solve the set covering problem proposed in the literature had some improvements which gave better solutions, i.e., better chromosomes in the first starting population, taking full account of domain specific knowledge with sound programming skill. We have further investigated the input data dependency of their genetic algorithm, i.e., the dependency on costs and density. We have found that for input problem data sets with densities greater than or equal to 3%, our genetic algorithm is still practical both in computing time and approximation ratio.

Indicators of global sustainable sourcing as a set covering problem:an integrated approach to sustainability

Sustainability describes a broad set of themes centered on current human uses of the planet’s resources.The multiple uses and users of the term have led to a proliferation of salient issues and associated indicators.We present a new method to systematically link these issues and indicators under two conceptual frameworks of sustainability in order to enable quantitative analyses.We demonstrate this approach with a specific use case focused on the global sourcing of agricultural products.We use the optimization software Marxan in a novel way to develop minimum sets of indicators that provide maximum coverage of sustainability issues.Minimum covering sets were identified and accumulation curves were developed to measure the contribution of each indicator in each set to overall issues coverage.While greater detail in the assessment of each indicator would likely provide more effective sets of indicators,those that were generated provide optimism that this approach can bring better focus to sustainability assessments.

Properties and Relations of Several Operators Based on Covering Rough Sets

The coveting rough sets theory is a generalization of traditional rough set theory, and can also describe information with incompleteness and fuzziness in information systems. In this paper, we first provide the definitions of several upper and lower covering approximation operators on the covering approximation space. Then, we study the properties of these operators. Finally, we propose the mutual relations between approximation operators and similar relations of the operator （ I ） based on the covering rough sets.

Numerical Characterizations of Covering Rough Sets Based on Evidence Theory

Covering rough sets are improvements of traditional rough sets by considering cover of universe instead of partition.In this paper,we develop several measures based on evidence theory to characterize covering rough sets.First,we present belief and plausibility functions in covering information systems and study their properties.With these measures we characterize lower and upper approximation operators and attribute reductions in covering information systems and decision systems respectively.With these discussions we propose a basic framework of numerical characterizations of covering rough sets.

Binding Number and Fractional k-Factors of Graphs

In this paper, we consider the relationship between the binding number and the existence of fractional k-factors of graphs. The binding number of G is defined by Woodall as bind(G)=min{ | NG(X) || X |:∅≠X⊆V(G) }. It is proved that a graph G has a fractional 1-factor if bind(G)≥1and has a fractional k-factor if bind(G)≥k−1k. Furthermore, it is showed that both results are best possible in some sense.

Minimum Covering RandićEnergy of a Graph

Randićenergy was first defined in the paper [1]. Using minimum covering set, we have introduced the minimum covering Randićenergy REC (G) of a graph G in this paper. This paper contains computation of minimum covering Randićenergies for some standard graphs like star graph, complete graph, thorn graph of complete graph, crown graph, complete bipartite graph, cocktail graph and friendship graphs. At the end of this paper, upper and lower bounds for minimum covering Randićenergy are also presented.

ENERGY-EFFICIENT HEURISTIC METRIC FOR SCP IN SENSOR NETWORKS

A heuristic metric is presented to achieve the optimal connected set covering problem （SCP） in sensor networks. The coverage solution with the energy efficiency can guarantee that all targets are fully covered. Among targets, the crucial ones are redundantly covered to ensure more reliable monitors. And the information collected by the above coverage solution can be transmitted to Sink by the connected data-gathering structure. A novel ant colony optimization （ACO） algorithm--improved-MMAS-ACS-hybrid algorithm （IMAH） is adopted to achieve the above metric. Based on the design of the heuristic factor, artificial ants can adaptively detect the coverage and energy status of sensor networks and find the low-energy-cost paths to keep the communication connectivity to Sink. By introducing the pheromone-judgment-factor and the evaluation function to the pheromone updating rule, the pheromone trail on the global-best solution is enhanced, while avoiding the premature stagnation. Finally, the energy efficiency set can be obtained with high coverage-efficiency to all targets and reliable connectivity to Sink and the lifetime of the connected coverage set is prolonged.

Collaborative planning approach for anti-bioterrorism emergency facility location based on aerodynamics

To smooth the correlation process from bio-virus diffusion to emergency relief response,the Gaussian plume model is used to describe the diffusion of dangerous sources,where the bio-virus concentration at any given point in affected areas can be calculated.And the toxic load rule is introduced to define the borderline of the dangerous area at different levels.Combined with this,different emergency levels of different demand points in dangerous areas are confirmed using fuzzy clustering,which allows demand points at the same emergency level to cluster in a group.Some effective emergency relief centers are chosen from the candidate hospitals which are located in different emergency level affected areas by set covering.Bioterrorism experiments which were conducted in Nanjing,Jiangsu province are simulated,and the results indicate that the novel method can be used efficiently by decision makers during an actual anti-bioterrorism relief.

Non standard pallet series designing problem in ammunition supply system

According to the compound packing problem in ammunition supply system in our army, the non-standard pallet series design model is proposed, and the original problem that can be solved as a set cover problem with a nested bin-packing problem, is analyzed, then two heuristic algorithms are applied to solve the problem.

An Approximation Algorithm for P-prize-collecting Set Cover Problem

In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=U.Every subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative profit.Our goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit bound.Our main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.

Restricted parameter range promise set cover problems are easy

The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.

Alliance Free and Alliance Cover Sets

A defensive （offensive） k-alliance in F = （V, E） is a set S C V such that every v in S （in the boundary of S） has at least k more neighbors in S than it has in V ／ S. A set X C_ V is defensive （offensive） k-alliance free, if for all defensive （offensive） k-alliance S, S／ X ≠ 0, i.e., X does not contain any defensive （offensive） k-alliance as a subset. A set Y C V is a defensive （offensive） k-alliance cover, if for all defensive （offensive） k-alliance S, S ∩ Y ≠ 0, i.e., Y contains at least one vertex from each defensive （offensive） k-alliance of F. In this paper we show several mathematical properties of defensive （offensive） k-alliance free sets and defensive （offensive） k-alliance cover sets, including tight bounds on their cardinality.

Cellular traffic offloading utilizing set-cover based caching in mobile social networks

To cope with the explosive data demands, offloading cellular traffic through mobile social networks（MSNs） has become a promising approach to alleviate traffic load. Indeed, the repeated data transmission results in a great deal of unnecessary traffic. Existing solutions generally adopt proactive caching and achieve traffic shifting by exploiting opportunistic contacts. The key challenge to maximize the offloading utility needs leveraging the trade-off between the offloaded traffic and the users＇ delay requirement. Since current caching scheme rarely address this challenge, in this paper, we first quantitatively interpret the offloading revenues on the cellular operator side associated with the scale of caching users, then develop a centralized caching protocol to maximize the offloading revenues, which includes the selective algorithm of caching location based on set-cover, the cached-data dissemination strategy based on multi-path routing and the cache replacement policy based on data popularity. The experimental results on real-world mobility traces show that the proposed caching protocol outperforms existing schemes in offloading scenario.

A Coevolutionary Algorithm for Many-Objective Optimization Problems with Independent and Harmonious Objectives

Evolutionary algorithm is an effective strategy for solving many-objective optimization problems.At present,most evolutionary many-objective algorithms are designed for solving many-objective optimization problems where the objectives conflict with each other.In some cases,however,the objectives are not always in conflict.It consists of multiple independent objective subsets and the relationship between objectives is unknown in advance.The classical evolutionary many-objective algorithms may not be able to effectively solve such problems.Accordingly,we propose an objective set decomposition strategy based on the partial set covering model.It decomposes the objectives into a collection of objective subsets to preserve the nondominance relationship as much as possible.An optimization subproblem is defined on each objective subset.A coevolutionary algorithm is presented to optimize all subproblems simultaneously,in which a nondominance ranking is presented to interact information among these sub-populations.The proposed algorithm is compared with five popular many-objective evolutionary algorithms and four objective set decomposition based evolutionary algorithms on a series of test problems.Numerical experiments demonstrate that the proposed algorithm can achieve promising results for the many-objective optimization problems with independent and harmonious objectives.

Secure coverage-preserving node scheduling scheme using energy prediction for wireless sensor networks

With the fast development of the micro-electro-mechanical systems （MEMS）,wireless sensor networks （WSNs） have been extensively studied.Most of the studies focus on saving energy consumption because of restricted energy supply in WSNs.Cluster-based node scheduling scheme is commonly considered as one of the most energy-efficient approaches.However,it is not always so efficient especially when there exist hot spot and network attacks in WSNs.In this article,a secure coverage-preserved node scheduling scheme for WSNs based on energy prediction is proposed in an uneven deployment environment.The scheme is comprised of an uneven clustering algorithm based on arithmetic progression,a cover set partition algorithm based on trust and a node scheduling algorithm based on energy prediction.Simulation results show that network lifetime of the scheme is 350 rounds longer than that of other scheduling algorithms.Furthermore,the scheme can keep a high network coverage ratio during the network lifetime and achieve the designed objective which makes energy dissipation of most nodes in WSNs balanced.

ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES

Let G=<V, E, L> be a network with the vertex set V, the edge set E and the length vector L, and let T* be a prior determined spanning tree of G. The inverse minimum spanning tree problem with minimum number of perturbed edges is to perturb the length vector L to L+ , such that T* is one of minimum spanning trees under the length vector L+ and the number of perturbed edges is minimum. This paper establishes a mathematical model for this problem and transforms it into a minimum vertex covering problem in a bipartite graph G0, a path-graph. Thus a strongly polynomial algorithm with time complexity O(mn2) can be designed by using Hungarian method.