Best model for Redistricting ?
53 views
Skip to first unread message
Harvey Frey
Aug 1, 2017, 1:24:24 PM8/1/17
to MiniZinc
I'm looking into political redistricting, and wonder what would be the best model
A sample problem would be:
7500 census tracts, each with coordinates and population
to be assigned to 53 districts.
constraint: populations of all districts to be within 1%
maximize: "compactness" of districts (ie: minimize gerrymandering)
This seems to be a fairly straightforward clustering problem with constraints.
But, in the tutorial, I see no mention of clustering problems.
The knapsack model of the tutorial wouldn't seem to accommodate the compactness requirement.
What would be the best model compatible with Minizinc?
A sample problem would be:
7500 census tracts, each with coordinates and population
to be assigned to 53 districts.
constraint: populations of all districts to be within 1%
maximize: "compactness" of districts (ie: minimize gerrymandering)
This seems to be a fairly straightforward clustering problem with constraints.
But, in the tutorial, I see no mention of clustering problems.
The knapsack model of the tutorial wouldn't seem to accommodate the compactness requirement.
What would be the best model compatible with Minizinc?
Jean-Noël Monette
Aug 6, 2017, 6:46:44 AM8/6/17
to mini...@googlegroups.com, Pierre Flener
Hi Harvey,
I don't think there is an existing MiniZinc global constraint specifically for this use case.
However, your problem (in particular the existence of a compactness requirement) reminds me of the sectorisation of airspace for air traffic control. Some of my former colleagues have worked on that problem and you might find some inspiration in their work, in order to build your own MiniZinc predicate and model. Here is a link to their paper: https://arxiv.org/abs/1401.7463 Have a look in particular at sections 5.1 (connectedness) and 5.2 (compactness).
Best,
Jean-Noël
I don't think there is an existing MiniZinc global constraint specifically for this use case.
However, your problem (in particular the existence of a compactness requirement) reminds me of the sectorisation of airspace for air traffic control. Some of my former colleagues have worked on that problem and you might find some inspiration in their work, in order to build your own MiniZinc predicate and model. Here is a link to their paper: https://arxiv.org/abs/1401.7463 Have a look in particular at sections 5.1 (connectedness) and 5.2 (compactness).
Best,
Jean-Noël
--
You received this message because you are subscribed to the Google Groups "MiniZinc" group.
To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/minizinc/9c01adac-4ab2-4a25-8d9e-1dcfbfaa5df4%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Alexander Schiendorfer
Feb 1, 2018, 11:19:04 PM2/1/18
to MiniZinc
Maybe MiningZinc could be useful for your purposes
Reply all
Reply to author
Forward
0 new messages