Heuristic solutions and confidence intervals for the multicovering problem

DOI10.1016/0377-2217(87)90142-1MaRDI QIDQ579132zbMATH OpenOpenAlexFDO

Authors David J. Gonsalvez, Nicholas G. Hall, Wansoo T. Rhee, Sue P. Siferd

Publication date 1987

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(87)90142-1

zbMATH Keywords

heuristicslarge scale computational studiesmulticover problems

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

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.

Recommendations

• The multicovering problem
• An efficient heuristic for large set covering problems
• scientific article; zbMATH DE number 3875302
• A probabilistic heuristic for a computationally difficult set covering problem
• A fast approximation algorithm for the multicovering problem

Cites work

• An efficient heuristic for large set covering problems
• scientific article; zbMATH DE number 3831680 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Interval estimation of a global optimum for large combinatorial problems
• On the quality of heuristic solutions to a 19\(\times 19\) quadratic assignment problem
• Procedures for Estimating Optimal Solution Values for Large Combinatorial Problems
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Using Confidence Limits for the Global Optimum in Combinatorial Optimization

Cited in

(4)

• Case study on statistically estimating minimum makespan for flow line scheduling problems.
• Maximizing cover probability by using multivariate normal distributions
• A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering
• Confidence in heuristic solutions?

This page was built for publication: Heuristic solutions and confidence intervals for the multicovering problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579132)