AN EXACT ALGORITHM FOR THE MAXIMAL COVERING PROBLEM

This article develops a robust, exact algorithm for the maximal coveri ng problem (MCP) using dual-based solution methods and greedy heuristi cs in branch and bound. Based on tests using randomly generated proble ms with problem parameters similar to those in the existing literature , the hybrid approach developed in this work appears to be effective o ver a wide range of MCP model parameters. The method is further valida ted on problems constructed from three real-world data sets. The exten sive computational study compares the new method with other existing e xact methods using problems that are as big, or larger than, those use d in previous work on MCP. The results show that the proposed method i s effective in most instances of MCP. In particular, it is shown that bounding schemes using Lagrangian relaxation are effective on MCP as a method of obtaining both exact and heuristic solutions. (C) 1996 John Wiley & Sons, Inc.