Preprocessing for a map sectorization problem by means of mathematical programming

• DOI: 10.1007/s10479-013-1447-8
• Publication Date: 2013-09-12T03:30:38Z
• Authors: Xin Tang; Ameur Soukhal; Vincent T’kindt
• Keywords: Theory of computation

The sectorization problem is a particular case of partitioning problems occurring in cartography. The aim is to partition a territory into sectors such that the statistical activity measure of each sector is as close as possible to a given target value. We model this as a problem of minimizing the maximum deviation among all the sectors between their activity measure and their target value. We propose a mathematical programming formulation for the problem, we add some valid inequalities to restrict the solution space and develop a preprocessing procedure to reduce the number of variables. Computational results on different maps highlight the strong efficiency of this reduction procedure.