Heuristic solutions and confidence intervals for the multicovering problem
type: Item
instance of: scholarly article
title: Heuristic solutions and confidence intervals for the multicovering problem
zbMATH Open document ID: 0624.90073
DOI: 10.1016/0377-2217(87)90142-1
author: David J. Gonsalvez
author: Nicholas G. Hall
author: Wansoo T. Rhee
author: Sue P. Siferd
published in: European Journal of Operational Research
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4014454
zbMATH Keywords: large scale computational studies
zbMATH Keywords: multicover problems
zbMATH Keywords: heuristics
reviewed by: Hartmut Noltemeier
MaRDI profile type: Publication
full work available at URL: 0377-2217(87)90142-1
OpenAlex ID: W2081000990
cites work: Q3037131
cites work: Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
cites work: On the quality of heuristic solutions to a 19\(\times 19\) quadratic assignment problem
cites work: Procedures for Estimating Optimal Solution Values for Large Combinatorial Problems
cites work: Using Confidence Limits for the Global Optimum in Combinatorial Optimization
cites work: Q4198056
cites work: Interval estimation of a global optimum for large combinatorial problems
cites work: Q4739657
cites work: An efficient heuristic for large set covering problems
description: scientific article; zbMATH DE number 4014454