Systematic Approach to Enforcing Contiguity Constraint in Trajectory-based Methods for Combinatorial Optimization

• US 20130218789A1
• Filed: 02/21/2013
• Published: 08/22/2013
• Est. Priority Date: 02/21/2012
• Status: Abandoned Application

• Current Assignee: University of South Carolina
• Original Assignee: University of South Carolina
• Inventors: Guo, Diansheng
• Application Number:
  US13/772,769
• Publication Number:
  US 20130218789A1
• Time in Patent Office: Days
• US Class Current: 705/317
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06Q 30/018 Certifying business or products
• CPC Class Codes: G06Q 50/26 Government or public services business processes related to the transportation industry G06Q50/40

Abstract

A computer implemented method for enforcing geographic contiguity of an optimization method for redistricting is described. The method includes randomly grouping a data set of objects into geographically contiguous districts, optimizing the objects by iteratively moving one or more objects between neighboring districts, wherein a relationship of objects is analyzed in each district to determine a minimal set of objects that will move together to maintain contiguity between districts, and generating one or more solutions for the data set.

Claims

1. A computer implemented method for enforcing geographic contiguity of an optimization method for redistricting comprising:

randomly grouping a data set of objects into geographically contiguous districts;

optimizing the objects by iteratively moving one or more objects between neighboring districts, wherein a relationship of objects is analyzed in each district to determine a minimal set of objects that will move together to maintain contiguity between districts; and

generating one or more solutions for the data set.

2. The method of claim 1, further comprising:

determining all cut points and bioconnected components in each district and identifying a multi-object move for each cut point.

3. The method of claim 1, further comprising optimizing population equality of districts.

4. The method of claim 1, further comprising optimizing compactness of districts.

5. The method of claim 1, wherein a trajectory-based optimization method is utilized to optimize the objects.

6. The method of claim 5, wherein the trajectory-based optimization method comprises a Tabu optimization algorithm.

7. The method of claim 5, wherein the trajectory-based optimization method comprises a local greedy search optimization algorithm.

8. The method of claim 5, wherein the trajectory-based optimization method comprises a Kernighan-Lin algorithm optimization algorithm.

9. The method of claim 1, further comprising presenting one or more solutions to a user via a graphical user interface.

10. A computer system comprising memory and a process, the computer system being configured to enforce geographic contiguity of an optimization method for redistricting by performing operations comprising:

randomly grouping a data set of objects into geographically contiguous districts;

optimizing the objects by iteratively moving one or more objects between neighboring districts, wherein a relationship of objects is analyzed in each district to determine a minimal set of objects that will move together to maintain contiguity between districts; and

generating one or more solutions for the data set.

11. The computer system of claim 10, wherein optimizing the objects comprises:

determining all cut points and bioconnected components in each district and identifying a multi-object move for each cut point.

12. The computer system of claim 10, the operations further comprising optimizing population equality of districts.

13. The computer system of claim 10, the operations further comprising optimizing compactness of districts.

14. The computer system of claim 10, wherein a trajectory-based optimization method is utilized to optimize the objects.

15. The computer system of claim 10, wherein the trajectory-based optimization method comprises a Tabu optimization algorithm.

16. A non-transitory computer-readable medium storing instructions that when executed by at least one processor cause the at least one processor to perform operations comprising:

randomly grouping a data set of objects into geographically contiguous districts;

optimizing the objects by iteratively moving one or more objects between neighboring districts, wherein a relationship of objects is analyzed in each district to determine a minimal set of objects that will move together to maintain contiguity between districts; and

generating one or more solutions for the data set.