Heuristic solutions and confidence intervals for the multicovering problem (Q579132)

The authors are reporting on large scale computational studies for randomly generated multicover problems: min cx s.t. Ax\(\geq b\), \(x\in \{0,1\}\), \(b\in {\mathbb{N}}_+\). The comparison of ten (pure) heuristics and two mixed heuristics (ALL 10: randomly selecting heuristics from the basic 10 in each step; TOP 5: randomly selecting one of the best five in each individual problem) shows f.e. that a TOP 5-heuristic in about 70 \% of all studies yields a better solution than any pure heuristic. Under the assumption that ALL 10-solutions are (stochastically) independent and follow a Weibull distribution, a maximum likelihood estimation of the parameters of the distribution yields some narrow confidence intervals. The computational study suggests that the optimal solution will lie very likely in these intervals.