Index

Abstract

As generalizations of the classic set covering problem (SCP), both the set K-covering problem (SKCP) and the set variable (K varies by constraint) K-covering problem (SVKCP) are easily shown to be NP-hard.  Solution approaches in the literature for the SKCP typically provide no guarantees on solution quality.  In this article, a simple methodology, called the simple sequential increasing tolerance (SSIT) matheuristic, that iteratively uses any general-purpose integer programming software (Gurobi and CPLEX in this case) is discussed.  This approach is shown to quickly generate solutions that are guaranteed to be within a tight tolerance of the optimum for 135 SKCPs (average of 67 seconds on a standard PC and at most 0.13% from the optimums) from the literature and 65 newly created SVKCPs.  This methodology generates solutions that are guaranteed to be within a specified percentage of the optimum in a short time (actual deviation from the optimums for the 135 SKCPs was 0.03%).  Statistical analyses among the five best SKCP algorithms and SSIT demonstrates that SSIT performs as well as the best published algorithms designed specifically to solve SKCPs and SSIT requires no time-consuming effort of coding problem-specific algorithms—a real plus for OR practitioners.

Keywords: Simple sequential increasing tolerance matheuristic, Set K-covering problem, Set variable K-covering problem, General purpose integer programming software.

Received: 13 October 2021 / Revised: 1 December 2021 / Accepted: 7 December 2021/ Published: 10 December 2021

Contribution/ Originality

This study documents a methodology that iteratively uses integer programming software to efficiently generate solutions that are guaranteed to be very close to the optimums for the set K-covering problem.  A significant benefit of this methodology is that no problem specific algorithm needs to be coded by the user.

1. INTRODUCTION

The set k-covering problem (SKCP) is a generalization of the classic set covering problem.  The SKCP involves finding the columns of an m x n 0-1 matrix that cover each row of the matrix at least k times at minimal cost (the classic set covering problem only covers each row at least once). The SKCP can be mathematically represented as the following integer program: 

Algebraic expression (1) is the objective function which must be minimized.  Inequalities (2) are the constraints that guarantee each row i is covered by at least k columns, and conditions (3) force each variable xj to be either 0 or 1.  The set variable K-covering problem (SVKCP) has the same formulation as the SKCP except that the value of K can be different for each of the m constraints in (2).  Note that, to the authors’ knowledge, no solution procedures or problem instances currently exist in the literature for the SVKCP.

The SKCP has a number of important real-world applications and plays a significant role in many areas, such as scheduling, location, marketing, logistics, computational biology, and wireless networks [1].  For example, in communication or distribution problems where reliability is important, it is not sufficient to cover each element only once.  Another application of the SKCP comes from the domain of bioinformatics.   Researchers divide chromosomes into two regions: hot spots, where chromosome recombination takes place, and haplotype blocks, which complement the chromosomes.  If we want each pair of the haplotype patterns to be distinguished by k or more mutations or single nucleotide polymorphisms (SNPs), then we have a robust tagging SNP problem which can be modeled as a SKCP [2].  

The SVKCP is a straightforward extension of the SKCP in which the K value can differ for each row constraint.  Although, to the authors’ knowledge, the SVKCP has not been explicitly studied in the literature, one can easily envision real-world applications of the SVKCP.  For example, if a geographic area needed to be serviced by fire stations, the optimal location of the fire stations could be formulated as a SVKCP.  Each row of the matrix in this SVKCP would represent a neighborhood that should be serviced by at least two fire stations (one primary and one backup), but some neighborhoods might need to be serviced by more than two fire stations (for example, a neighborhood with a hospital in it). 

It is important to note that the problems (SKCP and SVKCP) that are being addressed in this research both require that all rows of a matrix be covered by K columns at minimum cost (K varies by row for the SVKCP).  However, there are related problems in the literature that have similar names, but different objectives.  Specifically, the maximum set K-covering problem (MKCP) consists in selecting a subset of K columns from a given set of n columns, in such a way that the number of rows covered by the selected columns is maximized (see Lin and Guan [3]).  Another related problem is the K-set cover problem (K-scp) that seeks to cover all rows of a matrix with the minimum number of columns such that each column chosen can cover at most K rows (see HAE, et al. [4]).

As extensions of the classic set covering problem, both the SKCP and the SVKCP can easily be shown to be NP-hard.  To avoid the potential for excessive computing times, up to this point, solutions reported in the literature for the SKCP (note that the SVKCP has not previously been discussed in the literature) have not guaranteed the quality of their solutions.

Normally in the literature, for a set of test problem instances, approximate solution method results are compared to optimal or best-known results that were determined by executing an exact algorithm for a long period of time—sometimes up to 24 hours [5] or more!  Researchers assume that, if an approximate solution method performs well on a limited set of problem instances, it will perform well on other problems—this is the weakness of using approximate solution methods with no guaranteed bounds on solution quality.  Such approximate solution methods will be discussed in the next section and include methods by Al-Shihabi [6]; Pessoa, et al. [5]; Salehipour [7] and Wang, et al. [8]; Wang, et al. [9].

In this article a methodology first discussed in McNally [10] referred to as the simple sequential increasing tolerance (SSIT) matheuristic is used to quickly solve 135 SKCPs commonly used in the literature and 65 SVKCPs introduced in this article.  Lu, et al. [11] used SSIT to quickly (average of 88 seconds on a standard PC) generate solutions guaranteed to be close (average within 0.094% of the optimums) on 270 multidimensional knapsack problem (MKP) instances commonly used in the literature.  These results are far better than other published metaheuristic results for the MKP. Dellinger, et al. [12] used SSIT to quickly (average of 63 seconds on a standard PC) generate solutions guaranteed to be close (average within 0.080% of the optimums) on 51 generalized assignment problems (GAP) instances commonly used in the literature.  These results are very competitive with the best published solution methods for the GAP.   

The key feature of the SSIT solutions is that they are guaranteed to be within a tight tolerance of the optimum. Another important feature of SSIT is its iterative use of any general-purpose integer programming software (Gurobi and CPLEX in this article, but other software could be used just as easily).  This combined with a user-defined sequence of loosening tolerances and maximum execution times for each tolerance makes SSIT a very flexible solution methodology.  SSIT can be considered a matheuristic because it uses math programming combined with a heuristically determined sequence of tolerances and execution times.   Since SSIT takes advantage of the power of a general-purpose exact solution method, no problem-specific algorithm is required which can be a substantial time saver for operations research (OR) practitioners.     

In the next section, the relevant literature will be reviewed.  Then, a brief overview of the SSIT matheuristic will be provided in Section 3.  In Sections 4 empirical results obtained from using the SSIT matheuristic to solve 135 SKCPs will be discussed and statistically compared to the leading published solution approaches specifically designed to solve the SKCP.  In Section 5 empirical results for 65 SVKCPs will be presented.  This article will close with some conclusions and suggested future work.

2. RELEVANT LITERATURE

The five main solution approaches designed specifically to solve the SKCP that appear in the literature are:

DLLCCSM (diversion local search based on configuration checking and scoring mechanism). This algorithm is presented in Wang, et al. [8] and uses a local search algorithm.  First, to overcome the cycling problem in local search, the set k-covering configuration checking (SKCC) strategy is proposed.  Second, a cost scheme of elements is used to define a scoring mechanism.  Then, the SKCC strategy and scoring mechanism are combined to decide which subset should be selected as a candidate solution component. 

MLQCC (multilevel score heuristic with quantitative configuration checking). This algorithm is presented in Wang, et al. [9] and uses a local search algorithm.  To overcome the cycling problem in local search, a new quantitative configuration checking (QCC) is proposed.  Also, a subset property called subscore, redefines property score [8].  A new multilevel (ML) score heuristic, which is a linear combination of subscore and score is developed.    

SALEHIPOUR_HEURISTIC.  This algorithm is presented in Salehipour [7] and is a heuristic that first generates a lower bound and then builds a feasible solution from the lower bound.  The feasible solution is improved through a removal local search.

LP-MMAS_LS. This algorithm is presented in Al-Shihabi [6] and uses a hybrid algorithm consisting of linear programming, max-min ant system and local search.  The algorithm exploits the LP-relaxation solution by classifying the columns based on their reduced costs.

LAGRASP.   This algorithm is presented in Pessoa, et al. [5] and uses a hybrid GRASP (greedy randomized adaptive search procedure) Lagrangean heuristic that uses GRASP with a path-relinking heuristic that uses modified costs to obtain approximate solutions.

The performance of these five approximate solution methods on 135 SKCPs will be compared both empirically and statistically in a later section to results obtained from using several SSIT scenarios with Gurobi to solve these same 135 SKCPs.  However, it is important to remember that all the above-mentioned solution procedures are explicitly designed to solve the SKCP and more importantly provide no guarantees on solution quality!  This is in sharp contrast to our use of SSIT to solve SKCPs because SSIT uses strictly general-purpose software with no time-consuming algorithm coding required and does provide bounds on the solutions that it generates.

3. OVERVIEW OF THE SIMPLE SEQUENTIAL INCREASING TOLERANCE MATHEURISTIC

The motivation [10] behind the simple sequential increasing tolerance (SSIT) matheuristic is to try to have the best of two worlds.  Namely, SSIT makes use of state-of-the-art optimization software (such as CPLEX or Gurobi) combined with loosening tolerances to obtain solutions that are guaranteed within known and relatively tight tolerances of the optimum in a timely manner.  By using commercially available and state-of-the-art optimization software instead of highly complex specialized codes for the particular combinatorial optimization problem (COP) being solved, SSIT can be used in a straightforward manner by both OR practitioners as well as researchers with no problem-specific coding required.  The SSIT matheuristic is very flexible and robust because the user can specify the number of tolerances as well as their specific values based on their needs.  The maximum execution time for each tolerance is also specified based on the specific needs of the user.  Although the SSIT concept is very intuitive, this is the first article to discuss and quantify the benefits of using SSIT specifically to solve SKCPs. 

As indicated earlier, SSIT can be considered a multi-pass methodology in which the program terminates if the goal tolerance is met.  If it is not met, then the tolerance is “loosened” and the current best solution is used as input for the next step in the solution process.  The “loosened” tolerance allows the branch-and-bound tree in the commercial software to be pruned more quickly.  The worst-case scenario for SSIT is that it does not terminate until the sum of the maximum execution times for each tolerance is reached.  In this case, the software gap at termination will indicate how close the best SSIT solution is to the optimum.  Specifically, for a minimization COP, the optimization software provides the gap between the best lower bound and the best solution. 

The pseudo code below summarizes the SSIT methodology for a generic COP. 

3.1. SSIT Matheuristic

  1. Begin 
  2. Input the number of phases N
  3. Input tolerance T_i and maximum execution time t_i for phases i=1, ..., N
  4. Input COP details   
  5. Run integer programming software program to solve COP
  6. For 1<=i<=N-1,
  7. IF integer programming software running time in phase i is less than t_i or i=N, FINISH
  8. ELSE,
  9. Take best solution obtained from Phase i and save it as SOL_i.
  10. Run integer programming software program with SOL_i as the warm start and tolerance T_{i+1} and maximum execution time t_{i+1}.
  11. i=i+1
  12. LOOP through step 7-11 until FINISH.

The flow chart of SSIT is also provided in Figure 1.

The benefit of SSIT using general purpose integer programming software such as CPLEX or Gurobi and, at the same time, requiring no problem-specific coding is significant.  For the problems discussed in this article, all the software default settings were kept except the time and tolerance per SSIT pass. In particular, the OR practitioner or researcher does not need to develop code or test a problem-specific algorithm.  Furthermore, practitioners will find that there is a wealth of examples that come with most optimization software (definitely CPLEX and Gurobi), which are ready to run out of the box.

Figure-1. SSIT flowchart.

These templates often only require a few adjustments before they are ready to run domain specific combinatorial optimization problems. Practitioners can also quickly find answers to many software specific questions in the online forums and extensive manuals.  Additionally, for industrial systems that use SSIT, the performance of these systems is “automatically” improved when new versions of the optimization software are installed. 

It is important to note that there is no need to “optimize” either the number of tolerances used or their values as well as the execution times for each tolerance.  These values are both user and problem specific and can be easily adjusted to meet the users’ needs!

Although it is common for OR practitioners to use commercial software at the default tolerance for a fixed amount of time and use the best solution generated when the execution time “runs out”, SSIT provides an alternate to this approach that will be shown to provide bounded solutions quickly.

4. SKCP EMPIRICAL RESULTS

4.1. Problem Instances

In Beasley’s OR library there are set covering problems that are used by researchers to test algorithms developed to solve the set covering problem (SCP).  Sixty-five SCP instances are commonly used to solve weighted set covering problems (WSCP) in which the objective function coefficients are positive integers.  Specifically, data sets 4, 5, 6, A, B, C, D, E, F, G, and H are commonly used by researchers. These problem instances are summarized in Table 1 below.  In contrast, if the cost coefficients are all the same or typically all equal to one, then the problem is called a minimum cardinality set covering problem (MCSCP) or a uni-cost set covering problem.  This current research will focus on solving weighted SKCP and SVKCP instances.

Table-1. WSCP Instances from Beasley’s or Library.

Data Set
Rows
Columns
Density
Instances
SCP4
200
1000
2
10
SCP5
200
2000
2
10
SCP6
200
1000
5
5
SCPA
300
3000
2
5
SCPB
300
3000
5
5
SCPC
400
4000
2
5
SCPD
400
4000
5
5
SCPE
50
500
20
5
SCPNRE
500
5000
10
5
SCPNRF
500
5000
20
5
SCPNRG
1000
10,000
2
5
SCPNRH
1000
10,000
5
5

In the literature, it is common for researchers to use the following 135 SKCP instances based on Beasley’s SCP instances.  Specifically, researchers use the 45 problem instances in data sets 4, 5, 6, A, B, C, and D with three different K values.  How the K values are determined will now be given.  KMIN = 2 for all 45 problem instances.  KMAX has the same K value for all rows of a problem, but can differ for the 45 problem instances.  For a given problem instance (from data sets 4, 5, 6, A, B, C, and D), the KMAX value is equal to the sum of the ones in a row with the minimum number of ones.  KMED is equal to the ceiling of (KMIN + KMAX)/2.  Hence, researchers typically report algorithm results by K value, KMIN, KMED, and KMAX.

4.2. SSIT Results for the SKCP

In order to use the SSIT matheuristic to solve SKCPs, a sequence of increasing tolerances and corresponding maximum execution times must be specified and an integer programming software package must be selected.  The purpose of this article is to demonstrate that the SSIT matheuristic works with any integer programming software package.  Obviously, the better the selected optimization software is in terms of generating good solutions quickly, the better the solution generated by SSIT.

The authors considered two leading optimization software packages: CPLEX (12.9) and Gurobi (9.1).  Both of these are highly sophisticated general purpose optimization packages that are easy for practitioners and researchers to use to solve large-scale integer programming problems in particular.  Empirical testing on more than 50 combinatorial optimization problems using both CPLEX and Gurobi resulted in no statistical difference in either solution quality or execution time required given the same parameter settings for both software packages.  Hence, the authors decided to use both: Gurobi for the empirical analysis of the SKCPs and CPLEX for the empirical analysis of the new SVKCPs (discussed in Section 5).  Also, to demonstrate that SSIT is not PC dependent, two different PCs were used—one for the SKCP analyses and a different one for the SVKCP analyses.  The SKCPs will be analyzed using Gurobi on a computer with the following specifications: an AMD Ryzen 7 3700X 8-Core Processor and 16 GB RAM on Windows 10 Home 64-bit.  The number of threads is 8.   The SVKCPs will be analyzed using CPLEX on a computer with the following specifications: 16 GB RAM on Windows 10, Intel processor with 2.9 GHz, and 1000 GB hard drive.  By default, CPLEX uses a number of threads equal to the number of cores or 32 threads (whichever number is smaller). The operating system manages any contention for processors.  The PC used has 4 cores, so the number of threads is 4.  A thorough discussion of the performance of the latest versions of CPLEX versus Gurobi for solving combinatorial optimization problems is a topic for another article.  In this article the power and robustness of SSIT regardless of the integer programming software used or the PC used is demonstrated.

For the SSIT analysis of the SKCP, three SSIT scenarios (SSIT1, SSIT2, and SSIT3) were used.  Limited preliminary empirical analysis using the PC specified above for SKCPs indicated that tight bounds (less than 1%) could be achieved in under 600 seconds for even the most difficult problems tested.  Hence for this application, the total execution times would add to 600 seconds.  Three SSIT scenarios will demonstrate how shifting more execution time to the looser tolerances will for these 135 SKCPs reduces the average execution time.  The specifics of these three SSIT scenarios are given in Table 2.

Table-2. SSIT scenario execution times (seconds) for each tolerance.

Tolerances
0.0001
0.001
0.003
0.005
0.007
0.009
SSIT1
60
60
120
120
120
120
SSIT2
60
60
60
120
120
180
SSIT3
30
60
90
120
120
180

The results of executing the three SSIT scenarios for the 135 SKCPs are summarized in Table 3, 4, and 5.  Detailed results for all 135 SKCPs are available upon request. 

Table-3. Summary results averaged over 135 SKCPs.

SSIT scenario
Average guaranteed maximum deviation from optimum (%)
Average actual deviation from optimum (%)
Average execution
time (seconds)
SSIT1
0.136
0.032
84
SSIT2
0.137
0.032
75
SSIT3
0.131
0.030
67

In Table 3, results for each of the three SSIT scenarios (SSIT1, SSIT2, and SSIT3) are averaged over all 135 SKCPs.  The guaranteed maximum deviation from the optimum column shows the farthest away the SSIT solutions can be without knowing the exact value of the optimums.  Over all 135 SKCPs, the average guaranteed farthest deviations the SSIT solutions are from the optimums are 0.136%, 0.137%, and 0.131% for SSIT1, SSIT2, and SSIT3 respectively.  However, comparing these 135 SSIT solutions to known optimums or best-known solutions, the SSIT solutions, on average, actually only deviated 0.032%, 0.032%, and 0.030% from the optimums for SSIT1, SSIT2, and SSIT3 respectively. 

Additionally, these very impressive results required, on average, only 84 seconds, 75 seconds, and 67 seconds for SSIT1, SSIT2, and SSIT3 respectively.  For SSIT3, the execution times were 180 seconds or less for 120 of the 135 SKCPs (89%) and 120 seconds or less for 113 of the 135 SKCPs (84%).  There is next to no differences among the three SSIT scenarios in terms guaranteed maximum deviation from the optimum and actual deviation from the optimum.  However, the SSIT3 scenario has the smallest average execution time of 67 seconds which is a 20% reduction over the SSIT1 average execution time and an 11% reduction over the SSIT2 average execution time.

Table 4 shows average execution time and deviations for each SSIT scenario by KMIN, KMED, and KMAX.  The results in Table 4 indicate that, regardless of the SSIT scenario, the KMED SKCPs require the most effort to solve and the KMIN SKCPs require the least effort to solve.  However, regardless of SSIT scenario, even for the KMED problems, the average times are less than 180 seconds.  Except for time, the results differ very little by SSIT scenario.

Table 5 shows the distribution of the tolerances at which SSIT terminated based on SSIT scenario and K value.  As was evident from earlier analyses, the results differ very little based on the particular SSIT scenario.  For example, regardless of SSIT scenario, all 45 KMIN SKCPs terminated at the tightest tolerance of 0.0001.  As previously observed, again regardless of SSIT scenario, the KMED problems required the most effort to solve. 

Table-4. Average execution time and deviations for each SSIT scenario by KMIN, KMED, and KMAX.

Average guaranteed maximum deviation from optimum (%)
Average actual deviation from optimum (%)
Average execution
time (seconds)
KMIN
SSIT1
0
0
0.5
SSIT2
0
0
0.5
SSIT3
0
0
0.5
KMED
SSIT1
0.296
0.071
178.6
SSIT2
0.298
0.070
151.4
SSIT3
0.295
0.065
145.0
KMAX
SSIT1
0.111
0.025
73.0
SSIT2
0.113
0.027
71.9
SSIT3
0.114
0.023
54.4

The robustness of SSIT is that knowing the difficulty of the KMED instances (for example, from preliminary empirical analysis), if the OR practitioner wanted tighter guaranteed bounds for these problems and more computer time was not an issue, more time could be spent at the tighter tolerances.  Exactly how much time at each tolerance would depend on the particular application.  However, regardless of the SSIT scenario, the KMED SKCPs had a guaranteed maximum deviation from the optimum of under 0.3% (actual deviation of 0.07%) and average execution times under 180 seconds.          

Table-5. Termination tolerances distributions for each SSIT scenario by KMIN, KMED, and KMAX.

 
Tolerances
 
0.0001
0.001
0.003
0.005
0.007
0.009
KMIN
SSIT1
45
SSIT2
45
SSIT3
45
KMED
SSIT1
19
2
6
3
10
5
SSIT2
19
2
4
5
11
4
SSIT3
19
1
6
4
11
4
KMAX
SSIT1
20
2
23
SSIT2
20
3
20
2
SSIT3
16
7
21
1

Note: Comparisons of our SSIT results with the best published algorithms specialized specifically to solve the SKCP will now be given.

4.3. SKCP SSIT Results Compared to Other Metaheuristics

Although, as operations research practitioners, the authors appreciate the guaranteed bounds that the SSIT matheuristic provides, there may be readers that are interested in seeing how the SSIT solutions compared to the five best performing metaheuristics for the SKCP reviewed earlier in this article.  In Table 6, 7, and 8, the SSIT results for the 135 SKCPS typically used for empirical experiments by researchers will be compared to Wang, et al. [8]; Wang, et al. [9]; Salehipour [7]; Al-Shihabi [6] and Pessoa, et al. [5] discussed earlier in this article.   

Table-6A. Comparison of SSIT with Other Metaheuristics.

PROBLEM
KMIN
OPT/BKS
ALSHIHIBA
PESSOA
SALEH
WANG
2017
WANG
2019
SSIT1
SSIT2
SSIT3
SCP41
2
1148
1150
1150
1150
1148
1148
1148
1148
1148
SCP 42
2
1205
1205
1205
1205
1205
1205
1205
1205
1205
SCP 43
2
1213
1213
1214
1214
1213
1213
1213
1213
1213
SCP 44
2
1185
1189
1185
1185
1185
1185
1185
1185
1185
SCP 45
2
1266
1266
1266
1266
1266
1266
1266
1266
1266
SCP 46
2
1349
1349
1349
1352
1349
1349
1349
1349
1349
SCP 47
2
1115
1115
1115
1115
1115
1115
1115
1115
1115
SCP 48
2
1225
1225
1225
1225
1225
1225
1225
1225
1225
SCP 49
2
1485
1485
1485
1485
1485
1485
1485
1485
1485
SCP 410
2
1356
1360
1356
1359
1356
1356
1356
1356
1356
SCP 51
2
579
580
579
579
579
579
579
579
579
SCP 52
2
677
677
679
677
677
677
677
677
677
SCP 53
2
574
576
574
575
574
574
574
574
574
SCP 54
2
582
584
587
585
582
582
582
582
582
SCP 55
2
550
550
550
550
550
550
550
550
550
SCP 56
2
560
560
560
561
560
560
560
560
560
SCP 57
2
695
695
695
695
695
695
695
695
695
SCP 58
2
662
664
662
664
662
662
662
662
662
SCP 59
2
687
687
687
687
687
687
687
687
687
SCP 510
2
672
672
672
672
672
672
672
672
672
SCP 61
2
283
283
283
283
283
283
283
283
283
SCP 62
2
302
302
302
302
302
302
302
302
302
SCP 63
2
313
313
313
313
313
313
313
313
313
SCP 64
2
292
292
292
294
292
292
292
292
292
SCP 65
2
353
353
353
353
353
353
353
353
353

Table-6B. Comparison Of SSIT With Other Metaheuristics Results For Kmin Skcp Data Sets A, B, C, and D.

PROBLEM
KMIN
OPT/BKS
AL-SHIHIBA
PESSOA
SALEH
WANG 2017
WANG
2019
SSIT1
SSIT2
SSIT3
SCPA1
2
562
562
563
563
562
562
562
562
562
SCPA2
2
560
564
560
560
560
560
560
560
560
SCPA3
2
524
526
524
524
524
524
524
524
524
SCPA4
2
527
527
527
527
527
527
527
527
527
SCPA5
2
557
558
559
558
557
557
557
557
557
SCPB1
2
149
150
149
149
149
149
149
149
149
SCPB2
2
150
150
151
150
150
150
150
150
150
SCPB3
2
165
165
165
165
165
165
165
165
165
SCPB4
2
157
157
157
157
157
157
157
157
157
SCPB5
2
151
152
152
151
151
151
151
151
151
SCPC1
2
514
516
515
515
514
514
514
514
514
SCPC2
2
483
490
486
483
483
483
483
483
483
SCPC3
2
544
546
544
545
544
544
544
544
544
SCPC4
2
484
485
485
484
484
484
484
484
484
SCPC5
2
488
488
490
489
488
488
488
488
488
SCPD1
2
122
123
122
122
122
122
122
122
122
SCPD2
2
127
127
127
127
127
127
127
127
127
SCPD3
2
138
138
138
138
138
138
138
138
138
SCPD4
2
122
123
123
122
122
122
122
122
122
SCPD5
2
130
131
130
130
130
130
130
130
130

Table-7A. Comparison of SSIT With Other Metaheuristics Results for Kmed Skcp Data Sets 4, 5, and 6.

PROBLEM
KMED
OPT/BKS
AL-SHIHIBA
PESSOA
SALEH
WANG
2017
WANG
2019
SSIT1
SSIT2
SSIT3
SCP41
7
8350
8373
8366
8363
8352
8352
8350
8350
8350
SCP 42
6
6111
6123
6117
6118
6111
6111
6111
6111
6111
SCP 43
5
4676
4681
4690
4681
4676
4676
4676
4676
4676
SCP 44
5
4670
4683
4679
4674
4670
4670
4670
4670
4670
SCP 45
7
8389
8400
8409
8398
8392
8389
8389
8389
8389
SCP 46
6
6416
6427
6432
6419
6416
6416
6416
6416
6416
SCP 47
6
6281
6282
6284
6282
6281
6281
6281
6281
6281
SCP 48
7
8421
8435
8439
8427
8427
8424
8421
8421
8421
SCP 49
6
7101
7127
7121
7106
7101
7101
7101
7101
7101
SCP 410
5
5355
5367
5364
5358
5355
5355
5355
5355
5355
SCP 51
13
11205
11226
11239
11213
11209
11206
11205
11205
11205
SCP 52
14
14418
14443
14473
14436
14428
14424
14418
14418
14418
SCP 53
13
11476
11532
11513
11488
11487
11476
11476
11476
11476
SCP 54
12
9944
9970
9965
9956
9950
9948
9944
9944
9944
SCP 55
12
10880
10888
10918
10898
10895
10881
10880
10880
10880
SCP 56
12
10581
10609
10629
10597
10591
10582
10581
10581
10581
SCP 57
14
14919
14940
14984
14934
14946
14924
14919
14919
14923
SCP 58
12
10622
10539
10687
10635
10623
10622
10622
10622
10622
SCP 59
12
11042
11071
11081
11053
11049
11047
11042
11042
11042
SCP 510
13
12436
12469
12475
12451
12450
12436
12436
12436
12436
SCP 61
17
7653
7679
7692
7669
7653
7653
7653
7653
7653
SCP 62
16
6739
6760
6773
6752
6739
6739
6747
6747
6746
SCP 63
18
8309
8350
8365
8317
8309
8309
8309
8309
8309
SCP 64
18
8546
8569
8585
8567
8546
8546
8546
8546
8546
SCP 65
18
9038
9068
9070
9060
9038
9038
9038
9038
9038

Table-7B. Comparison of SSIT With Other Metaheuristics Results for Kmed Skcp Data Sets A, B, C, and D

PROBLEM
KMED
OPT/BKS
AL-SHIHIBA
PESSOA
SALEH
WANG
2017
WANG
2019
SSIT1
SSIT2
SSIT3
SCPA1
21
21224
21297
21324
21281
21241
21224
21236
21236
21241
SCPA2
21
21739
21810
21820
21793
21750
21740
21749
21753
21744
SCPA3
21
20095
20165
20155
20148
20126
20097
20113
20115
20102
SCPA4
22
22865
22959
22985
22916
22880
22880
22875
22866
22864
SCPA5
20
18643
18709
18706
18694
18660
18648
18641
18641
18646
SCPB1
61
29145
29214
29234
29218
29184
29145
29201
29211
29188
SCPB2
60
28075
28175
28187
28196
28124
28075
28135
28128
28109
SCPB3
59
27825
27934
27944
27899
27852
27825
27891
27878
27878
SCPB4
58
25664
25764
25742
25773
25695
25664
25707
25694
25703
SCPB5
60
28188
28295
28297
28310
28262
28188
28239
28247
28245
SCPC1
30
32613
32730
32763
32761
32648
32613
32646
32676
32639
SCPC2
31
32705
32837
32871
32848
32745
32705
32749
32776
32777
SCPC3
31
34428
34553
34610
34542
34451
34428
34496
34487
34477
SCPC4
30
31329
31466
31495
31472
31372
31329
31397
31364
31374
SCPC5
29
30030
30116
30196
30177
30061
30030
30082
30077
30087
SCPD1
82
38935
39091
39132
39073
38991
38935
39012
39022
39022
SCPD2
83
38935
39090
39098
39116
39038
38935
39035
39035
39037
SCPD3
81
39134
39256
39271
39314
39221
39134
39209
39209
39209
SCPD4
82
38723
38835
38879
38894
38814
38723
38798
38794
38814
SCPD5
83
40268
40401
40409
40404
40362
40268
40338
40342
40332

Table-8A. Comparison of SSIT With Other Metaheuristics Results for Kmax Skcp Data Sets 4, 5, and 6.

PROBLEM
KMAX
OPT/BKS
AL-SHIHIBA
PESSOA
SALEH
WANG
2017
WANG
2019
SSIT1
SSIT2
SSIT3
SCP41
11
18265
18265
18290
18273
18265
18265
18265
18265
18265
SCP 42
9
12360
12378
12405
12369
12370
12360
12360
12360
12360
SCP 43
8
10396
10397
10398
10396
10403
10396
10396
10396
10396
SCP 44
8
10393
10415
10427
10401
10396
10395
10393
10393
10393
SCP 45
11
18856
18861
18856
18863
18856
18856
18856
18856
18856
SCP 46
10
15394
15426
15419
15411
15404
15394
15394
15394
15394
SCP 47
10
15233
15261
15280
15249
15236
15233
15233
15233
15233
SCP 48
11
18602
18635
18628
18610
18613
18612
18602
18602
18602
SCP 49
10
16558
16586
16591
16563
16568
16562
16558
16558
16558
SCP 410
8
11607
11615
11618
11616
11607
11607
11607
11607
11607
SCP 51
24
35663
35722
35749
35679
35716
35685
35670
35670
35671
SCP 52
26
45396
45449
45433
45412
45428
45409
45396
45396
45396
SCP 53
24
36329
36374
36388
36349
36368
36343
36329
36329
36329
SCP 54
21
28017
28044
28051
28037
28035
28026
28017
28017
28017
SCP 55
22
32779
32808
32878
32795
32802
32788
32779
32779
32779
SCP 56
21
29608
29656
29653
29632
29632
29618
29608
29608
29608
SCP 57
25
41930
41964
41954
41944
41956
41946
41930
41930
41930
SCP 58
22
32320
32358
32405
32344
32344
32332
32320
32320
32320
SCP 59
22
33584
33600
33655
33602
33608
33599
33584
33584
33584
SCP 510
24
38709
38779
38807
38737
38756
38730
38709
38709
38709
SCP 61
31
23510
23559
23534
23536
23510
23510
23525
23523
23510
SCP 62
29
19934
19980
20025
19964
19940
19934
19952
19953
19956
SCP 63
34
27983
28021
28027
28014
27983
27983
27983
27983
27994
SCP 64
33
26442
26477
26530
26475
26446
26446
26456
26449
26450
SCP 65
33
27069
27090
27124
27084
27069
27069
27071
27071
27071

Table-8B. Comparison Of SSIT With Other Metaheuristics Results For Kmax Skcp Data Sets A, B, C, and D.

PROBLEM
KMAX
OPT/BKS
AL-SHIHIBA
PESSOA
SALEH
WANG 2017
WANG 2019
SSIT1
SSIT2
SSIT3
SCPA1
40
68507
68620
68669
68579
68590
68528
68518
68518
68518
SCPA2
39
65842
65940
65922
65881
65927
65863
65861
65861
65860
SCPA3
40
66829
66978
67016
66879
66891
66864
66839
66860
66863
SCPA4
41
72334
72436
72465
72398
72398
72351
72342
72338
72342
SCPA5
38
60491
60609
60625
60553
60539
60498
60503
60503
60503
SCPB1
119
105491
105580
105636
105522
105560
105491
105532
105532
105532
SCPB2
118
102883
102988
103046
103007
102941
102883
102937
102937
102912
SCPB3
115
98255
98334
98445
98400
98347
98255
98311
98311
98311
SCPB4
114
93729
93797
93836
93807
93800
93729
93783
93783
93760
SCPB5
118
102761
102878
102905
102822
102867
102761
102829
102832
102832
SCPC1
58
112471
112595
112667
112557
112565
112476
112538
112524
112501
SCPC2
59
113916
114017
114145
113974
114012
113925
113950
113950
113948
SCPC3
59
117416
117505
117680
117544
117501
117446
117454
117454
117449
SCPC4
58
110823
110945
111091
110935
110938
110851
110869
110869
110894
SCPC5
56
104428
104509
104591
104506
104518
104428
104457
104488
104427
SCPD1
162
144815
144891
145060
145055
144961
144815
144891
144935
144941
SCPD2
163
144020
144165
144218
144177
144138
144020
144182
144172
144141
SCPD3
159
140450
140542
140685
140655
140589
140450
140530
140609
140533
SCPD4
162
143391
143470
143582
143544
143488
143391
143504
143504
143497
SCPD5
163
146249
146308
146452
146373
146342
146249
146294
146294
146294

To try to determine how good heuristic solutions are, Pessoa, et al. [5] ran each of the 135 problem instances for up to 24 hours using CPLEX (Version 11).  Pessoa, et al. [5] found proven optimal solutions for all 45 KMIN instances, for 25 KMED instances, and for 25 KMAX instances.  Researchers typically compare their results to these CPLEX results.  The best-known solutions of Pessoa, et al. [5] were updated based on better solutions obtained by Wang, et al. [9] (in blue in the tables).  Best known solutions were also updated based on SSIT results (in red in the tables).

Table 6, 7, and 8 compare the results of using SSIT1, SSIT2, and SSIT3 as described previously in this article with the best results (over 10 independent runs) reported in Wang, et al. [8]; Wang, et al. [9]; Salehipour [7]; Al-Shihabi [6] and Pessoa, et al. [5] to solve the 45 SKCPs at KMIN, KMED, and KMAX respectively.

To make a simple comparison among the five previously published best performing SKCPs and the three SSIT scenario results for the 135 test instances, the average deviation from the optimum or best-known solution for each of the five solution methods are calculated over all 135 test instances. The average deviations from the optimum/BKS objective function value over all 135 problems for Al-Shihabi [6] was 0.20%, for Pessoa, et al. [5] was 0.23%, for Salehipour [7] was 0.13%, for Wang, et al. [8] was 0.05%, and for Wang, et al. [9] was 0.01%.  All three SSIT scenarios had the same (to two decimal places) average deviation from the optimum/BKS objective function value over all 135 problems of 0.03%.  All of these solution procedures generated very good results for the 135 test SKCP instances, with SSIT giving the second-best results at only an average 0.03% deviation from the optimums.  Detailed statistical analyses of these eight solution methods will be provided in Section 4.4. All three SSIT scenarios provide excellent bounds (guaranteed to be on average within a tolerance of 0.136%, 0.137%, and 0.131% of the optimums) for these 135 SKCPs with respectable average execution time of 84, 75, and 67 seconds for SSIT1, SSIT2, and SSIT3 respectively.

Let’s look a little closer at the major advantage that SSIT has over the other approximate solutions methods specifically when solving the SKCP.  It was just shown that Wang, et al. [9] on average only deviated 0.01% from the optimums for these 135 SKCPs.  In contrast, the three SSIT scenarios all performed “poorly” with an average deviation of 0.03% from the optimum for each SSIT scenario.  The real strength of SSIT, in the opinion of the authors of this article, is the fact that without expending excessive computer time to determine optimums, the SSIT scenario results are on average absolutely guaranteed to be within 0.136%, 0.137%, and 0.131% of the optimums for SSIT1, SSIT2, and SSIT3 respectively.  Additionally, SSIT obtains these excellent results using general purpose commercial software with default parameter settings—no specialized algorithms or computer codes are needed.  Furthermore, as pointed out earlier, leading integer programming software packages such as CPLEX and Gurobi offer a large number of pre-defined problem templates and customer support.
Finally, suppose that an OR practitioner was faced with the need to solve a SKCP for an actual real-world application and had access to CPLEX or Gurobi.  The OR practitioner could code the MLQCC algorithm of Wang, et al. [9] and solve his/her problem using MLQCC and obtain a solution that was probably very good, but exactly how good would be totally unknown.  Alternately, The OR practitioner could easily use SSIT in conjunction with CPLEX or Gurobi.  If the decision would have major financial implications for his/her corporation and the SKCP was very large, the OR practitioner might very well be willing to invest several hours of computing time to generate a solution that had a reasonably tight bound on it.  If the reader was the OR practitioner, would the reader use the Wang, et al. [9]; Salehipour [7] MLQCC algorithm or the SSIT methodology?

4.4. Statistical Analyses

In this section, with the 135 SKCP instances (45 KMIN instances, 45 KMED instances, and 45 KMAX instances), the three SSIT scenarios (SSIT1, SSIT2, and SSIT3) suggested in this article are compared to the top five SKCP solution methods Wang, et al. [8]; Wang, et al. [9]; Salehipour [7]; Al-Shihabi [6] and Pessoa, et al. [5] in the literature. Tukey’s pairwise comparison (after significant differences among the eight methods are detected from the one-way repeated measures ANOVA) is used for the three K values (KMIN, KMED, and KMAX). Tukey [13] the common significant level at 5% is applied in the analyses.

In the tables of the following sub-sections, Wang, et al. [8]; Wang, et al. [9], Saleh, Al-Shihiba, and Pessoa indicate Wang, et al. [8]; Wang, et al. [9]; Salehipour [7]; Al-Shihabi [6] and Pessoa, et al. [5] respectively. Table 9, 10, and 11 summarize the pairwise comparisons among the eight methods in terms of percent deviation from the optimum for KMIN, KMED, and KMAX, respectively. Note that the percent deviation from the optimum is getting smaller in order of A, B, C, and D, and methods that do not share a letter are significantly different.

4.4.1. Comparison – KMIN

Readers can check many results from Table 9 including (1) there is no statistically significant difference between Al_Shihiba and Pessoa and (2) there is no statistically significant difference among Saleh, Wang, et al. [8]; Wang, et al. [9], and the three SSIT scenarios (SSIT1, SSIT2, and SSIT3).

Table-9. Summary – Three SSIT scenarios vs. Top five methods. with KMIN.
Grouping Information Using the Tukey Method and 95% Confidence.

Method
N
Mean
Grouping
Al_Shihiba
45
0.0020897
A
Pessoa
45
0.0012286
A
B
Saleh
45
0.0007770
B
C
SSIT2
45
0.0000000
C
WANG 2019
45
0.0000000
C
WANG 2017
45
0.0000000
C
SSIT3
45
0.0000000
C
SSIT1
45
0.0000000
C

Note:  Means that do not share a letter are significantly different.

4.4.2. Comparison – KMED

In Table 10, readers can check many results such as (1) Pessoa shows the worst performance, (2) there is no statistically significant difference among Wang, et al. [8] SSIT1, SSIT2, and SSIT3 and (3) Wang, et al. [9] shows the best performance but the difference between SSIT3 and Wang, et al. [9] is not statistically significant.

Table-10. Summary – Three SSIT scenarios vs. Top five methods with KMED.
Grouping Information Using the Tukey Method and 95% Confidence.

Method
N
Mean
Grouping
Pessoa
45
0.0037011
A
Al_Shihiba
45
0.0026969
B
Saleh
45
0.0022919
B
WANG 2017
45
0.0008584
C
SSIT1
45
0.0007062
C
SSIT2
45
0.0007020
C
SSIT3
45
0.0006546
C
D
WANG 2019
45
0.0000800
D

Note: Means that do not share a letter are significantly different.

4.4.3. Comparison – KMAX

Readers can check many results from Table 11 including (1) there is no statistically significant difference between Saleh and Wang, et al. [8] and (2) there is no statistically significant difference among the four best performing methods - Wang, et al. [9] SSIT1, SSIT2, and SSIT3.

Table-11. Summary – Three SSIT scenarios vs. Top five methods with KMAX.
Grouping Information Using the Tukey Method and 95% Confidence.

Method
N
Mean
Grouping
Pessoa
45
0.0018616
A
Al_Shihiba
45
0.0011707
B
Saleh
45
0.0008030
C
WANG 2017
45
0.0006769
C
SSIT2
45
0.0002701
D
SSIT1
45
0.0002488
D
SSIT3
45
0.0002315
D
WANG 2019
45
0.0001604
D

Note:  Means that do not share a letter are significantly different.

In the next section, a test set of 65 SVKCP instances will be defined and solved using SSIT.

5. SVKCP EMPIRICAL RESULTS

5.1. SVKCP Data Sets

Since the SKCP instances commonly used in the literature to test SKCP solution approaches are based on SCPs from Beasley’s OR-library, the SVKCPs defined now will also be based on these SCPs as well as the SKCPs previously discussed.  The 65 SCPs from Beasley’s data sets 4, 5, 6, A, B, C, D, E, F, G, and H will be used to create SVKCPs.

Recall that, for a given SCP, KMAX is equal to the sum of the ones in a row with the minimum number of ones.  For each of the 65 SCPs mentioned above, the following 65 SVKCPs will be defined by randomly selecting integer K values for each row of the problem from the integers in the interval [2, KMAX].  In other words, instead of a fixed K value for all the rows of the problem (as is the case for SKCPs), the K values vary by row, but are integers randomly taken from the integers in the interval [2, KMAX].  For example, for SCP41, the interval would be from 2 to 11, so each row in the corresponding full interval SVKCP would have a K value of either 2, 3, 4, …,10, or 11.  The actual K values used for each row for the 65 SVKCPs, are available on the cloud at https://r3.res.outlook.com/owa/prem/images/xlsx_16x16.pngSVKCP_K-values.xlsx

5.2. SSIT for the SVKCP

To demonstrate that SSIT performs well on other PCs, software, and scenarios, the 65 SVKCPs just defined were solved using CPLEX on a PC with specifications: 16 GB RAM on Windows 10, Intel processor with 2.9 GHz, and 1000 GB hard drive.  By default, CPLEX uses a number of threads equal to the number of cores or 32 threads (whichever number is smaller). The operating system manages any contention for processors.  The PC used has 4 cores, so the number of threads is 4.  For these SVKCPs, only one SSIT scenario is used.  Specifically, the SSIT scenario used for the 65 SVKCPs was 0.001 at 300 seconds, 0.003 at 60 seconds, and 0.005 for 60 seconds.  This scenario contrasts with the SSIT scenarios used for the 135 SKCPs because for this scenario most of the time is spent at the tightest tolerance. The SSIT solution details for these SVKCPs are provided in Table 12.

From Table 12, one can see that all SSIT solutions for the 65 SVKCPs are guaranteed to be within 0.1% of the optimum and only required an average of 12.2 seconds to solve each SVKCP and 120 out of the 130 SVKCPs (over 92%) required less than 2 seconds of solution time.  To demonstrate the power of the SSIT matheuristic, these 65 SVKCPs were solved in CPLEX with a tolerance of T= 0.0001 (the default) and up to one hour of execution time.  Of these 65 SVKCPs, 47 terminated within the one-hour time limit and hence had found solutions guaranteed to be within 0.01% of the optimum—optimum for all intent purposes.  However, 18 had not terminated after 3600 seconds of execution time. 

Table-12. SSIT Results for 65 SVKCPs.

T=0.001
T=0.001
Problem
OBJ FN
Time
Problem
OBJ FN
Time
SVKCP41
11019
0.14
SVKCPB1
65005
0.13
SVKCP42
6773
0.08
SVKCPB2
62609
0.47
SVKCP43
5619
0.09
SVKCPB3
59285
0.22
SVKCP44
6408
0.17
SVKCPB4
59069
0.25
SVKCP45
9860
0.03
SVKCPB5
63159
0.27
SVKCP46
8094
0.08
SVKCPC1
62757
0.61
SVKCP47
8355
0.06
SVKCPC2
62543
0.20
SVKCP48
9829
0.13
SVKCPC3
66477
1.19
SVKCP49
9153
0.17
SVKCPC4
63568
0.83
SVKCP410
6926
0.16
SVKCPC5
57532
0.64
SVKCP51
19615
0.14
SVKCPD1
99270
0.95
SVKCP52
25113
0.16
SVKCPD2
96204
0.66
SVKCP53
16488
0.14
SVKCPD3
97091
0.94
SVKCP54
15731
0.13
SVKCPD4
96351
1.84
SVKCP55
16488
0.09
SVKCPD5
95537
0.42
SVKCP56
14720
0.11
SVKCPNRE1
175154
1.02
SVKCP57
22186
0.13
SVKCPNRE2
174079
1.14
SVKCP58
18163
0.20
SVKCPNRE3
166165
1.56
SVKCP59
16318
0.08
SVKCPNRE4
161895
1.41
SVKCP510
22296
0.05
SVKCPNRE5
162255
1.14
SVKCP61
13185
0.22
SVKCPNRF1
178893
1.70
SVKCP62
11868
0.41
SVKCPNRF2
189989
1.59
SVKCP63
15527
0.67
SVKCPNRF3
189785
1.83
SVKCP64
15040
0.27
SVKCPNRF4
188813
1.13
SVKCP65
15847
0.36
SVKCPNRF5
196674
1.61
SVKCPA1
39046
0.44
SVKCPNRG1
217562
227.14
SVKCPA2
36828
0.34
SVKCPNRG2
215316
2.61
SVKCPA3
37781
0.16
SVKCPNRG3
219089
52.31
SVKCPA4
41455
0.22
SVKCPNRG4
221559
184.17
SVKCPA5
34844
0.39
SVKCPNRG5
227274
281.81
SVKCPNRH1
317145
3.00
SVKCPNRH2
320148
3.64
SVKCPNRH3
319924
3.53
SVKCPNRH4
315907
3.33
SVKCPNRH5
320799
3.50

Although all SSIT solutions for the 65 SVKCPs were guaranteed within 0.1% of the optimum, how did these solutions compare to the solutions that were found when CPLEX was executed at the default T=0.0001 tolerance?  As a simple comparison, the average objective function value for the 65 SVKCPs executed at T=0.0001 was 94042.6 and the average execution time was 1054.9 seconds compared to the SSIT average objective function value of 94084.0 and an average execution time of 12.2 seconds.  Hence, after the fact, the SSIT solutions were off from the solutions obtained by CPLEX with T = 0.0001 by 0.04%, but the SSIT execution time was only 1.2% of the CPLEX execution time.  Note that, even “before the fact”, the SSIT solutions were guaranteed within 0.1% of the optimum.

6. SUMMARY AND FUTURE WORK   

In this article the simple sequential increasing tolerance (SSIT) matheuristic is used to solve generalizations of the classic set covering problem such that bounded solutions are efficiently generated.  This multi-pass matheuristic is used in conjunction with integer programming software (in this case both Gurobi and CPLEX) and employs a sequence of increasing tolerances that are used with the integer programming software.  Best solutions found at one tolerance are then input as starting solutions for the next looser tolerance.  In addition to SSIT finding bounded solutions quickly, its use of general-purpose integer programming software (such as CPLEX or Gurobi) is a significant benefit to OR practitioners.  Specifically, it allows OR practitioners to quickly develop SSIT models using default software parameter values and templates with no need for problem-specific algorithms and corresponding computer code.  Based on the particular application, the user has the flexibility to set the number of tolerances as well as their values.  Additionally, the user determines the maximum execution time for each tolerance.  Furthermore, for industrial systems that use SSIT, the performance of these systems is “automatically” improved when new versions of the optimization software are installed.   

Specifically, the SSIT matheheurstic was shown to be highly effective and efficient at solving 135 set K-covering problems (SKCP) that appear in the literature.  Three SSIT scenarios were tested and average deviation from the optimum or best-known solution was 0.03% for all three scenarios over all 135 SKCPs with average execution times of 84, 75, and 67 seconds for SSIT1, SSIT2, and SSIT3 respectively.  Only one of the five published algorithms had a smaller average deviation and that was Wang, et al. [9] with an average deviation of 0.01%.  However, for the 135 problems, statistical analyses demonstrated that the difference between SSIT3 and Wang, et al. [9] was statistically insignificant.  Also, SSIT1 and SSIT2 results were statistically as good as Wang, et al. [9] for the KMIN and KMAX problems.  SSIT3 and Wang, et al. [9] were slightly better than SSIT1 and SSIT2 for the KMED problems.  What is much more important is that SSIT generated solutions that were guaranteed to be within a small percentage of the optimum while there are no solution quality guarantees for any of the other SKCP solution methods that appear in the literature.  Specifically, over all 135 SKCPs, SSIT found solutions guaranteed to be at most 0.136%, 0.137%, and 0.131% from the optimum for scenarios SSIT1, SSIT2, and SSIT3 respectively. 

This article introduced the set variable K-covering problem to be a SKCP in which the K value varies by row constraints.  Based on set covering problems from Beasley’s OR-Library, 65 SVKCPs were defined and effectively and efficiently solved using the SSIT matheuristic.  For these 65 SVKCPs, SSIT found solutions guaranteed within 0.1% of the optimum for all 65 problems in an average time of 12 seconds.

Finally, since the SSIT matheuristic is a general-purpose strategy for solving combinatorial optimization problems, the authors plan to test the performance of SSIT on solving other difficult-to-solve combinatorial optimization problems using several different commercial integer programming software packages. 

Funding: This study received no specific financial support.  

Competing Interests: The authors declare that they have no competing interests.

Acknowledgement: All authors contributed equally to the conception and design of the study.

REFERENCES

[1]          M. G. Resende, "An optimizer in the telecommunications industry," SIAM SIAG/Optimization Views-and-News, vol. 18, pp. 8-19, 2007.

[2]          C.-J. Chang, Y.-T. Huang, and K.-M. Chao, "A greedier approach for finding tag SNPs," Bioinformatics, vol. 22, pp. 685-691, 2006.Available at: https://doi.org/10.1093/bioinformatics/btk035.

[3]          G. Lin and J. Guan, "Solving maximum set k-covering problem by an adaptive binary particle swarm optimization method," Knowledge-Based Systems, vol. 142, pp. 95-107, 2018.Available at: https://doi.org/10.1016/j.knosys.2017.11.028.

[4]          E. HAE, E.-L. YMA, and A. SM, "A new approximation algorithm for k-set cover problem," Arabian Journal for Science and Engineering, vol. 41, pp. 935–940, 2016.Available at: https://doi.org/10.1007/s13369-015-1895-3.

[5]          L. S. Pessoa, M. G. Resende, and C. C. Ribeiro, "A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering," Computers & Operations Research, vol. 40, pp. 3132-3146, 2013.Available at: https://doi.org/10.1016/j.cor.2011.11.018.

[6]          S. Al-Shihabi, "A hybrid of max–min ant system and linear programming for the k-covering problem," Computers & Operations Research, vol. 76, pp. 1-11, 2016.Available at: https://doi.org/10.1016/j.cor.2016.06.006.

[7]          A. Salehipour, A heuristic algorithm for the set k-cover problem. Communications in Computer and Information Science 1173. Cham: Springer, 2020.

[8]          Y. Wang, M. Yin, D. Ouyang, and L. Zhang, "A novel local search algorithm with configuration checking and scoring mechanism for the set k-covering problem," International Transactions in Operational Research, vol. 24, pp. 1463-1485, 2017.Available at: https://doi.org/10.1111/itor.12280.

[9]          Y. Wang, C. Li, H. Sun, J. Chen, and M. Yin, "MLQCC: An improved local search algorithm for the set k-covering problem," International Transactions in Operational Research, vol. 26, pp. 856-887, 2019.Available at: https://doi.org/10.1111/itor.12614.

[10]        B. McNally, "A simple sequential increasing tolerance matheuristic that generates bounded solutions for combinatorial optimization problems," Master’s Thesis, Kutztown University of Pennsylvania, 2021.

[11]        Y. Lu, B. McNally, E. Shively-Ertas, and F. Vasko, "A simple and efficient technique to generate bounded solutions for the multidimensional Knapsacvk problem: A guide for OR practitioners," IOnternational Journal of Circuits, Systems, and Signal Processing, vol. 15, pp. 1650-1656, 2021.Available at: https://doi.org/10.46300/9106.2021.15.178.

[12]        A. Dellinger, Y. Lu, B. McNally, M. S. Song, and F. J. Vasko, "A simple and efficient technique to generate bounded solutions for the generalized assignment problem: A guide for OR practitioners," Research Reports on Computer Science, vol. 1, pp. 13-34, 2021.

[13]        J. Tukey, "Comparing individual means in the analysis of variance," Biometrics, vol. 5, pp. 99-114, 1949.Available at: https://doi.org/10.2307/3001913.

Views and opinions expressed in this article are the views and opinions of the author(s), Review of Computer Engineering Research shall not be responsible or answerable for any loss, damage or liability etc. caused in relation to/arising out of the use of the content.