Heuristic solutions and confidence intervals for the multicovering problem
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.
scientific article; zbMATH DE number 4014454