Coverage location problems and totally balanced relaxations: Simulation results

Several types of covering location models are easily solved if the underlying covering matrix is totally balanced. If the covering matrix is not totally balanced, it may be desirable to identify a minimal number of rows of columns to remove so that the remaining matrix is totally balanced. Problem decomposition can take advantage of this information. In this paper, the authors give a heuristic algorithm to remove undesirable rows or columns. This algorithm is tested on both randomly generated matrices and matrices arising from planar location problems. A significant finding is that matrices from planar location problems seem to have more desirable structure (fewer removed rows or columns) than comparable random matrices.