A Simple and Effective Methodology for Generating Bounded Solutions for the Set K-Covering and Set Variable K-Covering Problems: A Guide for or Practitioners

Authors

DOI:

https://doi.org/10.18488/journal.76.2021.82.76.95

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

Abstract Video

Downloads

Vasko F.J. (2024)
Efficiently Generating Bounded Solutions for Very Large Multiple Knapsack Assignment Problems. Journal of Computational and Cognitive Engineering, 3(1), 1-7.
10.47852/bonviewJCCE3202921
Dellinger A. (2023)
Simple strategies that generate bounded solutions for the multiple-choice multi-dimensional knapsack problem: a guide for OR practitioners. International Transactions in Operational Research, 30(6), 4061-4077.
10.1111/itor.13144
Mohyaldeen S.Y. (2022)
Periodic and breather solutions for miscellaneous soliton in metamaterials model by computational schemes. International Journal of Geometric Methods in Modern Physics, 19(12),
10.1142/S0219887822501961
Li R. (2022)
The nonlinear vibration and dispersive wave systems with cross-kink and solitary wave solutions. International Journal of Geometric Methods in Modern Physics, 19(10),
10.1142/S0219887822501511
Zhang X.Z. (2022)
Novel exact solutions, bifurcation of nonlinear and supernonlinear traveling waves for M-fractional generalized reaction Duffing model and the density dependent M-fractional diffusion reaction equation. Results in Physics, 37,
10.1016/j.rinp.2022.105485
Chen Z. (2022)
Extracting the exact solitons of time-fractional three coupled nonlinear Maccari's system with complex form via four different methods. Results in Physics, 36,
10.1016/j.rinp.2022.105400
Kopçasız B. (2022)
Novel exact solutions and bifurcation analysis to dual-mode nonlinear Schrödinger equation. Journal of Ocean Engineering and Science,
10.1016/j.joes.2022.06.007

Published

2021-12-10

How to Cite

McNally, B. ., Lu, Y. ., Shively-Ertas, E. ., Song, M. S. ., & Vasko, F. J. (2021). A Simple and Effective Methodology for Generating Bounded Solutions for the Set K-Covering and Set Variable K-Covering Problems: A Guide for or Practitioners. Review of Computer Engineering Research, 8(2), 76–95. https://doi.org/10.18488/journal.76.2021.82.76.95

Issue

Section

Articles