1 Introduction

Particle swarm optimization (PSO) is a nature-inspired, relatively recent meta heuristic developed by Kennedy and Ebehert (1995). Like genetic algorithms, the PSO is also an optimization technique based on the population i.e. based on trope of social behavior of group of birds (or) banks of fish. Basically PSO is inspired by the continuous movement of the particles that form swarm. Aiming to discrete problems and on several adaptations to those problems, modified PSO known as discrete particle swarm optimization (DPSO) has been proposed by Kennedy and Ebehert (1997).

1.1 Particle swarm optimization

The original PSO considers a swarm S containing n particles \( \left( {S = \{ 1, \, 2, \ldots ,n\} } \right) \), each particle i of the swarm has its position vector \( x_{i} = \left( {x_{i1} ,x_{i2} , \ldots ,x_{ij} , \ldots ,x_{im} } \right) \) and its velocity vector \( v_{i} = \left( {v_{i1} ,v_{i2} , \ldots ,v_{ij} , \ldots ,v_{im} } \right) \) in a m-dimensional continuous solution space. Initially particles positions and its velocities are obtained randomly within some limits. Each iteration, particles update their position and velocity. The position of the particle exclusively depends on its velocity i.e. when considering the kth iteration the position of the particle i is given by means of recurrent equation

$$ x_{i}^{k} = x_{i}^{k - 1} + v_{i}^{k} $$
(1)

But when updating the velocity, we must take into account of its velocity, attractiveness of its very own best position (b i ) and the best position (g i ) of its social neighbourhood N(i) because each particle i of the swarm communicate with its social neighbourhood or environment N(i) ⊆ S and which can change dynamically. One can experience this statement practically, when considering the movement of a fish, it find its best position either by adjusting its position or by his experience and their companions experience about the position. The equation of the velocity update of a particle in the swarm according to Kennedy and Eberhart (1995) is given by

$$ v_{i}^{k} = c_{1} \xi v_{i}^{k - 1} + c_{2} \xi \left( {b_{i} {-}x_{i}^{k - 1} } \right) + c_{3} \xi \left( {g_{i} {-}x_{i}^{k - 1} } \right) $$
(2)

The magnitude of the velocity is controlled by the parameter c 1, represents the effect of inertia, in order to avoid the indefinite increase of the velocity. The parameters c 2 and c3 are the positive constant weights representing the confidence degree of the particle i in different positions that regulates its movements. ξ is a random number uniformly distributed in [0, 1], generated independently at each iteration.

1.2 Discrete particle swarm optimization

The algorithm described above is the formal particle swarm optimization (PSO) method applicable only for continuous problems. Because of variety of applications of discrete problems and aiming towards their applications, Kennedy and Eberhart (1997) designed discrete binary version of the PSO, referred as discrete particle swarm optimization (DPSO) method, with discrete variables. They defined particles trajectories and velocities in terms of changes of probabilities that a bit will be in one state (or) the other. i.e. position of each particle is a vector \( x_{i} = \left( {x_{i1} ,x_{i2} , \ldots ,x_{ij} , \ldots ,x_{im} } \right) \) where x ij assumes the value 1 if the jth binary variable within the position of the ith particle, otherwise it assumes the value 0. However velocity of each particle is still a vector \( v_{i} = \left( {v_{i1} ,v_{i2} , \ldots ,v_{ij} , \ldots ,v_{im} } \right) \) of the m-dimensional continuous space, \( v_{i} \in \Re^m \). Here v ij indicate the probability of x ij assumes a value 0 (or) 1 in the next iteration. To set the ith particle new position value, each position variable x ij is randomly set with the probability of selecting a value 1 using the sigmoid function (1 + exp(−v ij ))−1 where v ij is restricted to some typical value |v ij | < 6.0, prevents the probability of the x ij assuming either a value of 0 (or) 1 from being too high. Kennedy and Eberhart (1997) have shown that this DPSO capable of optimizing several combinatorial optimization problems.

Few more DPSO techniques for discrete optimization problems are discussed below. Secrest (2001) presented a non-binary version of the DPSO. In this DPSO, the particles in the swarm were represented as linked list of cities and the move of the swarm operated by genetic operators mutation and recombination. Al-kazemi and Mohan (2002) developed a method by adopting the same strategy applied in Kennedy and Eberhart (1997), with the exemption that the coefficients are restricted to assume the values 1 and −1. To obtain the best solution with in the given number of iterations, they used two phase strategy. In the first phase, the coefficient (1, −1, 1) used by each ith particle, by directing the particle movement toward its social neighbourhood best position g i . In the second phase, the coefficient (1, 1, −1) used by each ith particle, by directing the particle movement toward its best position b i .

Yang et al. (2004) considered a larger number of combinations of the coefficients, which were referred as quantum states of the particles and they applied principles of quantum computing to update the velocity of the particle. Martinoli (2006), presented a multi-valued PSO (MVPSO). It is described with variables with mulitiple discrete values. In this PSO, position of each particle expressed by means of 3 dimensional array x ijk represents the probability that the ith particle, in the jth iteration, assumes the kth value. Sigmoid distribution used to generate the elements x ijk and they followed the Eqs. (1) and (2).

Another DPSO algorithm was developed by Correa et al. (2006) to tackle the data mining task of attribute selection, in order to classify data sets into classes (or) categories of the same type. This DPSO slightly differs from other PSO by means of swarm which contains particles representing combinations of selected attributes of different size, varies from 1 to λ, the total number of attributes. Other than that of best position of particle and best position among its neighbours, one more factor length of the particle is introduced. The new length of the particle is determined by selecting random number k ∈ [0, λ] and finally new position of the particle is updated by the k attributes with the largest likelihood in the velocity vector.

Tasgetiren et al. (2007) presented a DPSO to solve the generalized traveling salesman problem. In this DPSO, particles best position are updated using three operators which were presented in Pan and Tasgetiren (2008) and global neighbourhood best position updated by the same model applied in Kennedy and Eberhart (1997). Further to improve the solution quality they hybridized the DPSO with a variable neighbourhood descend local search. Liaoa et al. (2007) presented DPSO for flow shop scheduling problem. This DPSO designs “job-to-position” representation for the discrete particle. They define the position and velocity of the ith particle position in the tth iteration as \( X_{i}^{t} = \left( {x_{i11}^{t} ,x_{i12}^{t} , \ldots ,x_{inn}^{t} } \right),\quad x_{ijk} \in \left\{ {0,1} \right\}, \) where x tijk equals 1 if job j of particle i is placed in the kth position of the sequence and 0 otherwise and \( V_{i}^{t} = \left( {v_{i11}^{t} , \, v_{i12}^{t} , \ldots ,v_{inn}^{t} } \right),\quad v_{ijk}^{t} \in R, \) where \( v_{ijk}^{t} \) is the velocity value for job j of particle i placed in the kth position at iteration t respectively. The velocity \( V_{i}^{t} \), called velocity trail, is inspired by the frequency-based memory which records the number of times that a job visits a particular position.

Al-Sherbaz et al. (2010) used the DPSO method described in Kennedy and Eberhart (1997) for Wimax parameter adaptation through baseband processor, in this DPSO the solution space is the number of bits to represent a particle \( x_{i}^{t} \), This number of bits is determined by the range and the necessary precision of the optimized parameters. Shi et al. (2007) presented a novel DPSO based algorithm for Traveling Salesman Problem. In this DPSO, they introduced a permutation and also an uncertainty searching strategy to speed up the convergence speed. The ith particle position \( x_{i} = \left( {x_{i1} ,x_{i2} , \ldots ,x_{ij} , \ldots ,x_{im} } \right) \) represents the traveling circle of \( x_{i1} \to x_{i2} \to \cdots , \to x_{im} \to x_{i1} \). Therefore they used the (1) as it is but in (2) they considered the ξ as a real vector whose dimensions are corresponds to the number of transpositions dotted with them. Chen et al. (2006) developed a new hybrid approximation algorithm based on DPSO, this combines global search and local search to search for the optimal results and they also applied simulated annealing to avoid local optima and hence they updated the Eq. (2) using some control parameters. More DPSO based techniques are referred in Aliguliyev (2010), Qiang et al. (2009), Wang and Yang (2007), Zhang et al. (2007).

1.3 Jumping particle swarm optimization

García and Pérez (2008) introduced a new DPSO technique for discrete optimization. In this DPSO particles best position (or) improved solution based on the attraction caused by attractor, one can found this inspiration in frogs in nature; this method is called jumping particle swarm optimization (JPSO). This JPSO technique works without the components of velocity and inertia due to lack of continuous movement in the discrete space. These two are the main components in the original PSO technique. Instead of these components, a random component in the form of jumps is included for the movement of the particles. The position of the particles updated as similar to the velocity update in the general PSO, but in which weights of the update equation are interpreted as probabilities of the movement of the particles by random (x i ) or by guided attraction of its own position (b i ) or by attraction of best position of its social neighbourhood (g i ) or by attraction of the best global position (g *). These attractions cause some improvement in the position of the particles. The update equation of particles position is given by

$$ x_{i} = c_{1} x_{i} + \, c_{2} b_{i} + \, c_{3} g_{i} + \, c_{4} g* $$

where c 1, c2, c3 and c4 are the probability values of the movement of the particles towards their corresponding attracted positions. For the probability values the unit interval [0, 1] is divided into four segments with lengths c 1, c2, c3 and c4 = 1 − (c 1 + c2 + c3). A random number generated corresponding to the segments and based on the random number which belongs to the segment, random improvement movement towards the attractor are applied to the position of the particle. The moves by the attraction that do not produce improvement are rejected. After each movement, the number generated at random is multiplied by p and by corresponding coefficients c i . If this product is greater than 1 a new move is applied, otherwise the movement stops until the next generation, and this move is rejected if it does not give improvement to its position. In addition, after each random or attractor movement, a local search is applied to every particle in the swarm. This local search approach explores set of possible moves starting from random one and the first move found that improve the particles current position. This improvement move stops if it does not give improvement to the current position of the particles.

This new methodology is successfully applied to the vehicle routing problem with time windows (Gutiérrez et al. 2008) and to the minimum labelling steiner tree problems (Consoli et al. 2010). This paper aims to apply JPSO to the Set covering problems (SCP), a well known combinatorial optimization problems, not only due to its spirit of nature but also due to its simplicity, easy implementation, less computational cost and time. Further we wish to compare this method with the other algorithms proposed for SCP to find out its effectiveness for solving SCP.

The rest of the paper is as follows: Sect. 2 explains the set covering problem. Section 3 discusses briefly on different SCP algorithms so far found in the literature. The pseudo-code and description of the proposed Jpso–scp algorithm and brief description of algorithms considered for comparison are discussed in Sect. 4. In Sect. 5 detailed experimental study and computational results are given and finally Sect. 6 ends with our conclusion.

2 Set covering problem

The set covering problem is a well-known combinatorial optimization problem with variety of real time applications in different fields, in particular crew scheduling in railway and airlines (Housos and Elmoth 1997), location problem of facility (Vasko and Wilson 1984) and in industry production planning (Vasko and Wolf 1987). The description of the SCP is as follows:

Given a finite set \( I = \left\{ {1, \, 2, \ldots ,m} \right\} \) of m elements and the family \( J = \left\{ {S_{1} ,S_{2} , \ldots ,S_{n} } \right\} \) of subsets of I such that a non-negative cost c j is associated with each subset S j . The set covering problem is to find the minimum size subset C ⊆ J such that all the members of I covered by the members of C with minimum total cost. i.e. for each i ∈ I, there exist at least one S j ∈ J such that i is covered by S j . Let A = (a ij ) be the m×n matrix whose jth column is the characteristic vector of the subset S j . i.e. a ij  = 1 if i is covered by S j or otherwise a ij  = 0. Then the 0–1 integer programming formulation of SCP is

$$ {\text{Min}}\,\mathop \sum \limits_{j = 1}^{n} c_{j} x_{j} \quad {\text{subject to}} $$
$$ \mathop \sum \limits_{j = 1}^{n} a_{ij} x_{j} \ge 1,\quad \,i = 1\,\,{\text{to}}\, m. $$
$$ x_{j} \in \left\{ {0,1} \right\}, \quad j = 1 \,{\text{to}} \,n. $$

The variable x j takes the value 1 if the subset S j is selected into the set cover and 0 otherwise. A particular version of the problem was introduced by Toregas et al. (1971), called unicost set covering problem (USCP) or minimum cardinality set covering problem (MCSCP) or location set covering problem (LSCP). In this version the associated cost c j , for all the elements in J, is equal and all may considered be equal to 1. It is well known that SCP and USCP are NP-hard (Garey and Johnson 1979) and are therefore difficult to solve in the case of large set of instances. A probabilistic version of the set covering problem is addressed in Saxena et al. (2010).

3 Related works

Many exact and heuristic procedures have been developed to solve the SCP. Exact procedure is mainly based on branch and bound (Balas and Carrera 1996), branch and cut and Gomory cut (Fisher and Kedia 1990). Still these procedures are able to solve very limited size instances and also consuming very large amount of time. Because of this many researchers focused on the developing heuristics to get optimal or near optimal solutions in a reasonable amount of time.

The following are the list of some metaheuristic approaches proposed for the SCP or unicost SCP. A very clear literature survey till 2000 on both heuristic and exact approaches has been presented in Caprara et al. (2000). This survey outlined their main characteristics and presented an experimental comparison on the test-bed instances of Beasley’s OR Library. Ceria et al. (1998) presented a heuristic based on Lagrangian method for solving large-scale SCP developed from the problem of crew-scheduling at the Italian Railways. Brusco et al. (1999) developed a heuristic for the SCP based on morphing procedure in a simulated annealing (SA). Yagiura et al. (2006) proposed a local search algorithm for SCP with three characteristics and they claimed through computational experience with other existing heuristic algorithms that their algorithm performed quite effectively for large-scale SCP instances. In Li and Kwan (2004), one can see fuzzy evaluation based evolutionary technique for large-scale SCP originated from the public transport industry. Simple solutions of random SCP instances through the average case analysis are discussed in Telelis and Zissimopoulos (2005) and solutions are constructed through an O(nm) algorithm. A Meta-RaPS (Meta-heuristic for Randomized Priority Search) approach to solve the SCP is discussed by Lan et al. (2007) investigates the development of an effective heuristic to solve the SCP and they claimed that their approach finds good quality solution for unicost SCP among compared heuristics. GRASP algorithm to solve unicost set covering problem presented in Bautista and Pereira (2007). This algorithm incorporates a local improvement procedure based on the heuristics to solve binary constraint satisfiability problems (SAT). Azimi et al. (2010) proposed a heuristic algorithm based on the electromagnetism metaheuristic approach to solve the unicost SCP. In this method a local search and iterations movement has been applied using “electromagnetism” theory to generate a pool of solutions from the initial population. Ren et al. (2010) proposed a new approach based on ant colony optimization (ACO) to solve the SCP. In this approach when choosing a new column, it first randomly selects an uncovered row and only considers the columns covering this row, rather than all the unselected columns as candidate solution components. Then a kind of dynamic heuristic information called Lagrangian dual information associated with currently uncovered rows. Finally, a simple local search procedure is developed to improve solutions constructed by ants while keeping their feasibility.

When considering Genetic algorithm approaches for the SCP, we can give importance to the following: Beasley and Chu (1996) developed a genetic algorithm approach for SCP. The method in this procedure modifies the basic genetic procedures by including a fitness-based crossover operator, a variable mutation rate and a heuristic feasibility operator and using these procedures they have designed an optimal algorithm for SCP. Through computational results they have claimed that their approach is capable of finding good quality solution for the SCP in reasonable time. Aickelin (2002) presented a new type of indirect genetic algorithm for the set covering problem. In this approach actual solutions are found by an external decoder function, results can be further improved by adding another indirect optimization layer and then optimized by another hill-climbing algorithm. A parallel genetic algorithm (PGA) model to solve the set-covering problem is presented in Solar et al. (2002). An experimental study obtained with a binary representation of the SCP, shows that PGA performs better than the sequential model in terms of the number of generations (computational time) needed to achieve solutions.

Li and Cai (2012), Balachander and Kannan (2010) developed gravitational search algorithm (GSA) for solving SCP. This GSA technique is one of the nature based technique like genetic algorithm, simulated annealing and ant colony optimization. It comprises a population based technique induced by Newton law of gravity and the law of motion. The main frame work of the algorithm is: objects are considered with different masses. Every mass can see the position of the other masses and the gravitational force transfers the information among the different masses. The heavy masses corresponds to good solution of the problem and the different masses attracted by the heaviest mass which would give optimum solution in the search space.

Other than these approaches an artificial neural network algorithm is developed by Ohlsson et al. (2001) for SCP based on the mean field feedback procedure. In this approach inequality constraints are encoded in convenient way using a multi-linear penalty function. They claimed through computational results that their algorithm outperformed other approximate methods. Galinier and Hertz (2007) developed three exact algorithms for large-scale SCP. Cormode et al. (2010) presented an algorithm for SCP using modern disk technology and they claimed through computational experiments that their algorithm finds good solutions for larger datasets.

Computational experience of different approximation algorithms with the SCP were given in Grossman and Wool (1997), Pardalos et al. (2006). In which the first paper conducted a comparative study of nine different approximation algorithms for the SCP which includes greedy variants, fractional relaxations, randomized algorithms and a neural network algorithm. Through computational experience on random problems, they identified that the best algorithm among those tested was a randomized greedy algorithm, with the neural network algorithm which is very close in second place. The second paper conducted an empirical study of approximation algorithms of Vertex Cover and the SCPs and produces their strengths, weaknesses, and operation. They have shown through computational experiments that the proven performance of all tested algorithms that did not forecast the empirical performance.

The following are the two problems, which are slightly associated with set covering problem and for these problems PSO based technique has been proposed. Zhan et al. (2012) proposed a binary particle swarm optimization (BPSO) approach to solve the disjoint set covers problem (DSC) in the wireless sensor networks. The DSC problem plays a vital role in sensor networks to increase the life length of sensor nodes. The DSC problem is to divide the sensor nodes into different disjoint sets and schedule them to work one by one in order to save energy while at the same time it should meet the full coverage, and the objective is to maximize the number of disjoint sets. Through simulation and computational results they claimed that the BPSO technique performed well over other approaches in maximizing the disjoint set covers. Moirangthem et al. (2012) proposed an approach based on PSO to identify the break point set in directional loops and multiloop settings and coordination of directional relays in system protection. In this approach they have converted the problem into set covering problem and then determined the break point set using PSO based technique.

4 Algorithms considered

This section describes the algorithms that we consider for the Set Covering problem: Ant_cover + ls, an ACO based approach by Ren et al. (2010); Meta-RaPS, a Meta-heuristic by Lan et al. (2007); IGA, an indirect genetic algorithm by Aickelin (2002) and finally the proposed Jpso–scp algorithm based on the Jumping particle swarm optimization.

4.1 Ant_cover + ls method

This Ant_cover + ls approach to the SCP follows the standard algorithmic scheme of Max–Min Ant system by Stützle and Hoos (2000) with some new features. Strategies used in this scheme include solution construction method, heuristic scheme, phenomerone update rule and a local search procedure. In the solution construction part each ant starts with an empty solution and add columns iteratively until all the rows are covered.

At a step t, an ant chooses column j from all the unselected columns according to probabilistic state transition rule. For this they must use all the possible combinations of state transition rule with the number of columns, and due to this factor its computational running time grows exponentially. Some heuristic rules based on the Lagrangian relaxation (Wolsey 1998) and local search approaches used in order to reduce the running time and computational cost. After running all the iterations, the best solution to date represents the output of the method.

4.2 Meta-RaPS method

This Meta-RaPS approach follows a meta-heuristic developed by Whitehouse et al. (2002). The main work of Meta-RaPS is the use of randomness as a mechanism to avoid local optima. At each iteration it constructs a feasible solution through the utilization of construction heuristic in randomized fashion, and then applies an improvement heuristic to improve the feasible solution.

In the SCP construction heuristic, to select a column for the feasible solution, a priority rule is applied. A greedy score for each column is calculated using some parameter and a column with lower greedy score gets highest priority. After this to improve the solution quality an improvement heuristic based on neighbourhood search procedure is applied. To improve the computational speed a preprocessing method and neighbor search procedure applied. After a number of iterations a best solution is then reported.

4.3 IGA method

The IGA approach to the SCP is a self tuning genetic algorithm and it solves the problem indirectly. This algorithm differs from previous evolutionary approaches by taking indirect route. This can be done by splitting the search into three distinct phases. Initially, the genetic algorithm finds permutations of the rows to be covered along with suitable parameters for the second stage.

The second stage consists of a decoder that builds a solution from the permutations using some provided parameters. These procedures built only exploitable solutions and the obtained solutions further fine tuned by hill-climbing approach. Over all more complicated strategies are applied to get an optimal solution.

4.4 Proposed Jpso–scp method

Even though repetitive advancements in computing, we are to be very wondered by the variety and adaptability of the natural world around us. Bio-inspired optimization and computing techniques covers wide variety of computational approaches motivated from the application of biology to optimization problems and is one of the major subset of natural computation. Making the above statement is worthy, a discrete PSO named Jpso–scp, based on the Jumping particle swarm optimization proposed by García and Pérez (2008), is chosen to deal with the set covering problem. The main interest of using this procedure is not only due to its spirit of nature but also due to its simplicity, easy implementation, low computational cost and time.

The procedure of the proposed Jpso–scp algorithm for the SCP is as follows: a swarm S, containing n particles (random solutions), in the JPSO procedure is considered as initial position of the particles in Jpso–scp too. Particles position x i (at some iteration i) develop in the solution space, jumping from one solution to another. By the effect of some attractors, at each iteration each particle has a random behaviour or random jumps. The position of a particle encoded as a feasible solution to the SCP. Movement of the particle i is influenced by three attractors:

  1. 1.

    Its own best position to date (b i )

  2. 2.

    The best position of its social neighbourhood (g i )

  3. 3.

    The best position to date obtained by all the particles which is called global best position (g*)

A jump towards the attractor based on the current solution feature and the feature of the attractor and a random jump is based on selecting at random feature of the solution and changing its value. For the SCP, features of a solution are the columns, covers maximum number of rows, to be included in the solution. A particle performs a jump with respect to the selected attractor means by randomly adding some columns to its current position from the selected attractor, or dropping some columns from its current position that are not included in the attractor.

Pseudo-code of the Jpso–scp algorithm given in Algorithm 4.41

figure a
figure b
figure c
figure d
figure e

Description of the Jpso–scp follows:

Initial position of the swarm S are generated by using the initial population algorithm given by Beasley and Chu (1996). According to population based model, this is the best choice for the initial positions of the swarm. Here x i represent one random feasible solution. In the swarm containing n particles (n random solutions), the ith particle position x i is a 0–1 vector denoting which columns are present in the particle i. Particles positions are updated in every iteration. When considering the kth iteration, ith particle obtain a new position \( x_{i}^{k} \) from its previous position \( x_{i}^{k - 1} \) by using the following update equation

$$ x_{i}^{k} = \, c_{1} x_{i}^{k - 1} + \, c_{2} b_{i} + \, c_{3} g_{i} + \, c_{4} g* $$

i.e. position \( x_{i}^{k} \) is obtained by making random moves from its current position \( x_{i}^{k - 1} \) with probability c1, approaching jumps towards b i with probability c2, towards g i with probability c3, or towards g* with probability c4 = 1 − (c1 + c2 + c3). In the SCP, by giving equally likely probability for each of the jumps, the values of c1, c2, c3 and c4 are set to 0.25. i.e. a random number α between 0 and 1 is generated and if α belongs to \( \left[ {0, 0.25} \right[ \), the particle perform a random jump from its current position x i . Otherwise if α belongs to \( \left[ {0.25, 0.5} \right[ \), the movement of the particle x i aiming towards the attractor b i . Instead, if α belongs to \( \left[ {0.5, 0.75} \right[ \), the particle x i attractor is selected as g i for its movement. For the remaining case, i.e. if α belongs to \( \left[ {0.75, 1} \right[ \), g* is selected as attractor for the movement of the particle x i .

When the ith particle making the jump towards the selected attractor, the particle x i either drops some columns from x i , or randomly adds some columns from the selected attractor based on the procedure in Algorithm 4.41.1. In this procedure to make the solution feasible, we make use of the concept of heuristic feasibility operator (Beasley and Chu 1996), which not only maintains the feasibility of the solutions but also refines the solution towards the optimality. Adding or dropping of some columns of x i in Algorithm 4.41.1 make use of the following heuristic procedure. In this procedure a random integer \( \mu \) is selected between 0 and |x i |. Successively, it either drops some columns from x i or adds some columns from selected attractor until \( \mu \) columns have been added or deleted from the x i . After this phase, the set of uncovered rows by x i are updated. If it is identified, a greedy heuristic approach is applied in order to maintain the feasibility of the solution. i.e. for each uncovered row, correspondingly a column with low cost ratio included and to maintain the optimality a local optimization technique is applied to remove any redundant columns in the solution.

Further to refine the updated solution, as a final phase of the Jpso–scp, a local search procedure developed in Ren et al. (2010), known to be best for SCP, is applied in order to remove redundant columns from x i and replace them with associated low cost columns that cover corresponding rows at the same time that retaining the feasibility. i.e. this procedure try to remove high cost first whenever it is possible. The detailed description of this phase follows: For each solution C constructed by Jpso–scp, let n i be the number of columns covering a row i, \( i \in I \) and it is ≥1 because of the feasibility of the solution. For each j \( \in \) C, let R j  = {i/n i  = 1 \( \forall i \in \) r j } be the set of rows only covered by column j. If |R j | = 0, it implies that column j is redundant and it can be removed directly. On the other side if |R j | = l > 0, there are l number of rows covered by column j exclusively and in this case the cost of the column j is compared with total cost of all the columns \( minC_{i} \), \( i \in R_{j} \) where \( minC_{i} \) is the column with the minimal cost among all the columns covering row i. If the cost of the column j is greater, the column j is replaced by all the columns \( minC_{i} \). After these add or drop phase of the columns to the solution C, the value of n i is updated. As explained in Solar et al. (2002), no operation is done when |R j | ≥ 3 because of less improvement in the solution quality and the relatively high computational cost, pseudo-code of this local search procedure given in the Algorithm 4.41.2.

5 Experimental studies

To test the performance of the proposed heuristic, it has been evaluated experimentally on the 65 benchmark instances of SCP from Beasley’s OR Library (Beasley 1990). These benchmark instances classified into 11 groups depends on the number of instances, rows and columns and density. Here density represents the number of non-zero entries in the SCP matrix. This information is in the Table 1 in detail. All the experiments were carried out on an Intel Pentium Core2 Duo Processor PC having 1.6 GHz CPU and 1 GB RAM. All the procedures of the Jpso–scp algorithm have been coded and implemented in MATLAB.

Table 1 Brief summary of SCP test instances
Full size table

To carry out the effectiveness of the proposed Jpso–scp algorithm, comparison made with the following three best known methods of SCP:

  • Ant_cover + ls: ACO based approach by Ren et al. (2010)

  • Meta-RaPS: Meta-heuristic by Lan et al. (2007)

  • IGA: Indirect Genetic Algorithm by Aickelin (2002)

The proposed Jpso–Scp approach is purely based on the spirit of nature, so we wish to test our proposed approach not only with the nature based approaches but also with a well known meta-heuristic approach. In the above mentioned three algorithms first and third methods are nature based technique and the second one is a meta-heuristic approach. In the mean time, it is important to note that all the four algorithms ran on the same platform.

A maximum CPU time allowed is chosen as the stopping criterion for all the four algorithms. This criterion will be useful for the direct comparison of all the algorithms with respect to their quality of solution. It is denoted by mCPU in the table.

For each test set, based on the density percentage, 100 SCP test instances are created. All the four algorithms ran on these 100 instances, run for mCPU time and, in each case, the best solution is recorded and the average objective function value is noted.

Results obtained by all the four algorithms are shown in the Table 2, in which first and second column represents instances name and their corresponding best known solution or optimum objective function value, highlighted by bold numbers, correspondingly the instances where the proposed and compared algorithms reaches the optimal solution are highlighted by bold numbers in their columns. In columns three, four, five and six O avg and T avg (s) represents the average objective function value and average time taken in seconds produced by each algorithm to find out the best known solution. More over we identified that the proposed algorithm found optimum solution for 60 instances out of 65 instances in all the 100 runs whereas Ant-Cover + ls found optimum for 55 out of 65 instances, Meta-RaPS and IGA found optimum for 53 and 45 instances respectively. In at least one of 100 runs, our proposed Jpso–scp algorithm found optimum solution for all the 65 instances whereas it was 64, 63 and 60 for Ant-Cover + ls, Meta-RaPS and IGA respectively.

Table 2 Test results for each instance (mCPU = 500 s)
Full size table

Further to identify the effectiveness of the proposed algorithm, we have calculated the average of average time taken for each set in the total of 11 set of instances and these results are plotted in the Fig. 1. From this figure we can see that, when compared to other algorithms, the proposed Jpso–scp algorithm took very less average running time for all the 11 set of instances. Further we have calculated the percentage of mean deviation of the average optimum value obtained by all the algorithms from the best known solution or optimum solution using the relation {(O avg  − Opt) × 100}/Opt and the obtained results are plotted in Fig. 2 and it indicates that the percentage of mean deviation of average objective function value of Jpso–scp algorithm is very small when compared to other three algorithms.

Fig. 1
figure 1

Average time taken for each set of instances

Full size image
Fig. 2
figure 2

Mean % of deviation of average values of objective function

Full size image

Further in order to confirm the effectiveness of the proposed approach, we follow the rank based statistical analysis; a similar analysis presented in Consoli et al. (2010). For each data set, the ranks of the algorithm are evaluated based on the following performance metric of an algorithm. The performance of an algorithm is considered as better than another one; if in a shortest computational time it obtains either maximum average objective function or an equal average objective function value. The algorithm with best performance assigned with rank 1, rank 2 is assigned to the second best one, and so on. The average ranks of the algorithms among the considered set of instances are IGA = 3.62; Meta-Raps = 2.85; Ant-cover + ls = 2.46 and Jpso–Scp = 1.29. These rank values indicate that the performance of the Jpso–Scp is the best, followed by Ant-cover + ls, Meta-Raps and IGA. This evaluation technique further confirms the superiority of the Jpso–Scp over other compared heuristics.

To analyse the statistical significance of difference between evaluated ranks, we make use of a statistical test for comparison of algorithms. For more detailed study about different tests on comparison of algorithms we can refer (Demśar 2006; Hollander and Wolfe 1973) and the test considered in this work is Nemenyi Post-hoc test (1963). This test is very much useful to identify the performance of two algorithms significantly differs or not. It considers the performance of two algorithms that are significantly different if their corresponding average ranks differ by at least a specific threshold critical difference. Based on this test at 1 % level of significance the critical difference value is 1.05. Table 3 shows that the difference between the average ranks of the algorithms and these results enumerate that the obtained values are greater than the critical difference when other algorithms are compared with Jpso–scp approach. These table values and the smallest rank of Jpso–Scp further insists that the performance of Jpso–scp approach is the best one for solving Set covering problem.

Table 3 Pairwise difference between the average ranks of the algorithms
Full size table

6 Conclusions

In this paper, a new JPSO based approach, Jpso–scp is proposed for solving the set covering problem. This approach finds best solution to SCP in three phases. In the first phase an attractor is selected using row and column cover conditions with low total cost and based on this attractor a feasible solution is then constructed. This feasiblity is refined for optimality in the second phase and in the third phase redundant columns are removed. i.e. the refined solution in the second phase has been refined further in the third phase. This causes improved quality solution with low computational cost. Extensive computational results show that this approach produces high quality solution in very short running time. Comparison with well known approaches of SCP yield that the proposed Jpso–scp approach based on jumping discrete particle swarm optimization method get tremendous appreciation in solving the SCP by outperforming those approaches. Further, the simplicity, less computational cost and very short running time of the proposed approach imply that the jumping discrete particle swarm optimization based approach is an attractive alternative approach for hard combinatorial optimization problems.