Re: [boost] BGL question about districting

Subject: Re: [boost] BGL question about districting
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-03-02 12:33:01

Barend Gehrels wrote:
> We're about an automated districting tool. We want to create Y
> districts 
> from X polygons, all having a specific value (e.g. area or
> inhabitants), where the total value of each district is as similar as
> possible and 
> each district is also as similar as possible. Let's call the value the
> "potential".
> 
> Of course this problem is NP-hard so we're glad with the first
> solution 
> or e.g. the first ten solutions.

What a fun problem!

First off your graph is a planar graph, that makes things easier.  Planar graph partitioning is computationally less expensive than general graph partitioning because min-cut is shortest path in a planar graph.  Constructing the graph ought to be trivial if the polygons that the districts are modeled as share a identical edge where they abut.  Just sort the edges with district ID and make graph edges between districts when identical edge geometries end up adjacent in the sorted sequence.

The hard part is the NP-hard part, of course.  For that I think you can model it as ILP and use a commerical (or free) solver.  It kind of depends on the scale.  You can partition the problem and use the ILP within sufficiently small partitions to recover runtime if the the scale of the problem is too large for the solvers and the optimality you sacrifice is small.  If you aren't concerned too much about optimality you can just implement a huristic partitioning algorithm, perhaps multi-level partitioning, that will be very speedy and produce good quality results.

Luke