zbMATH — the first resource for mathematics

An exact algorithm for the maximal covering problem. (English) Zbl 0846.90076
Summary: This article developes a robust, exact algorithm for the maximal covering problem (MCP) using dual-based solution methods and greedy heuristics in branch-and-bound. Based on tests using randomly generated problems with problem parameters similar to those in the existing literature, the hybrid approach developed in this work appears to be effective over a wide range of MCP model parameters. The method is further validated on problems constructed from three real-world data sets. The extensive computational study compares the new method with other existing exact methods using problems that are as big, or larger than, those used in previous work on MCP. The results show that the proposed method is effective in most instances of MCP. In particular, it is shown that bounding schemes using Lagrangian relaxation are effective on MCP is a method of obtaining both exact and heuristic solutions.

90C09 Boolean programming
90B80 Discrete location and assignment
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI