Algorithms for maximum independent set applied to map labelling
Tycho Strijk, A.M. Verweij, Karen Aardal · 2000
We consider the following map labelling problem: given distinct points p 1, p 2,..., p n in the plane, and given σ, find a maximum cardinality set of pairwise disjoint axis-parallel σ× σ squares Q1, Q2,..., Qr. This problem reduces to that of finding a maximum cardinality independent set in an associated graph called the conflict graph. We describe several heuristics for the maximum cardinality independent set problem, some of which use an LP solution as input. Also, we describe a branch-and-cut algorithm to solve it to optimality. The standard independent set formulation has an inequality for each edge in the conflict graph which ensures that only one of its endpoints can belong to an independent set. To obtain good starting points for our LP-based heuristics and good upper bounds on the optimal value for our branch-and-cut algorithm we replace this set of inequalities by the set of inequalities describing all maximal cliques in the conflict graph. For this strengthened formulation we also generate lifted odd hole inequalities and mod-k inequalities. We present a comprehensive computational study of solving map labelling instances for sizes up to n = 950 to optimality. Previously, optimal solutions to instances of size n ≤ 300 have been reported on in the literature. By comparing against these optimal solutions we show that our heuristics are capable of producing near-optimal solutions for large-scale instances.