Patent ID: 8259007

Claim:
A tangible computer readable media containing a series of instructions that when executed by one or more processors performs a process for partitioning a selected area into a predetermined number of contiguous partitions comprising: a. decomposing said selected area into a plurality of cells; b. computing a supply value for each of said plurality of cells; c. creating a network structure by connecting each of said plurality of cells to each of its neighboring cells by a plurality of bi-directional arcs, each of said bi-directional arcs is assigned: i. a cell commonality value configured to represent demand similarities between two adjacent cells; and ii. a flow variable configured to represent a cumulative supply value transferred between adjacent cells for each direction; d. selecting a subset of said plurality of cells to be a plurality of seeds, each of said plurality of seeds is assigned a demand variable; e. creating an optimization program to cluster said plurality of cells into said predetermined number of contiguous partitions including: i. calculating a total partition demand for each of said predetermined number of contiguous partitions as the summation of said supply value of cells clustered into each of said predetermined number of contiguous partitions; ii. developing an objective function that prioritizes said plurality of bi-directional arcs relative to their said cell commonality value; and iii. developing a set of constraints including: 1. creating said predetermined number of contiguous partitions; 2. applying flow conservation constraints to each of said plurality of cells; 3. limiting said total partition demand of each of said predetermined number of contiguous partitions to be smaller than a first predetermined value; and 4. for each of said plurality of cells, restricting only one of outflow variables to be non-zero; f. solving said optimization program to determine: i. the value for said flow variable for each of said plurality of bi-directional arcs; ii. a plurality of open seeds, each of said plurality of open seeds representing one partition; and iii. said total partition demand for each of said predetermined number of contiguous partitions; and g. creating partition boundaries for each of said plurality of open seeds by: i. creating an updated plurality of bi-directional arcs by eliminating arcs in said plurality of bi-directional arcs that their said flow variable is determined by said optimization program to be equal to zero; ii. grouping cells in said plurality of cells when they are connected to each other via one of said updated plurality of bi-directional arcs into a plurality of cell clusters; and iii. merging cells within each of said plurality of cell clusters to create said predetermined number of contiguous partitions.