Column-generation based bounds for the Homogeneous Areas Problem

This paper introduces a column generation approach to compute a lower bound for the problem. Since the pricing subproblem is NP-hard, we solve it with a Tabu Search algorithm, before applying a suitably strengthened multi-commodity flow formulation. Moreover, we also compute an upper bound for the overall problem with a primal heuristic based on the idea of diving and limited discrepancy search. The computational results refer to two real-world instances, a class of realistic instances derived from them, and two different classes of random instances.