0
# Optimization
1
2
Single-metric optimization and specialized analysis including Gingles analysis for Voting Rights Act compliance. Optimization algorithms find extreme or optimal districting plans within the space of valid partitions.
3
4
## Capabilities
5
6
### Single-Metric Optimization
7
8
Find partitions that maximize or minimize a specific evaluation metric while satisfying constraints.
9
10
```python { .api }
11
class SingleMetricOptimizer:
12
def __init__(
13
self,
14
proposal: ProposalFunction,
15
constraints: Union[ConstraintFunction, List[ConstraintFunction]],
16
accept: AcceptanceFunction,
17
initial_state: Partition,
18
maximize: bool = True
19
) -> None:
20
"""
21
Create optimizer for single metric optimization.
22
23
Parameters:
24
- proposal (ProposalFunction): Function to propose new partitions
25
- constraints (Union[ConstraintFunction, List[ConstraintFunction]]): Validation constraints
26
- accept (AcceptanceFunction): Acceptance function
27
- initial_state (Partition): Starting partition
28
- maximize (bool): Whether to maximize (True) or minimize (False) the metric
29
30
Returns:
31
None
32
"""
33
34
def optimize(self) -> Tuple[Partition, float]:
35
"""
36
Run optimization to find extreme partition.
37
38
Returns:
39
Tuple[Partition, float]: (best_partition, best_score)
40
"""
41
```
42
43
Usage example:
44
```python
45
from gerrychain.optimization import SingleMetricOptimizer
46
from gerrychain.metrics import efficiency_gap
47
48
# Define metric function
49
def eg_metric(partition):
50
return abs(efficiency_gap(partition["SEN18"]))
51
52
# Set up optimizer to minimize efficiency gap
53
optimizer = SingleMetricOptimizer(
54
proposal=recom,
55
constraints=constraints,
56
accept=always_accept,
57
initial_state=partition,
58
maximize=False # Minimize efficiency gap
59
)
60
61
# Run optimization
62
best_partition, best_score = optimizer.optimize()
63
print(f"Best efficiency gap: {best_score:.4f}")
64
```
65
66
### Gingles Analysis
67
68
Specialized analysis for Voting Rights Act compliance, focusing on minority representation opportunities.
69
70
```python { .api }
71
class Gingles:
72
def __init__(
73
self,
74
proposal: ProposalFunction,
75
constraints: List[ConstraintFunction],
76
accept: AcceptanceFunction,
77
initial_state: Partition,
78
minority_column: str,
79
threshold: float = 0.5
80
) -> None:
81
"""
82
Create Gingles analyzer for VRA compliance analysis.
83
84
Analyzes ability to create districts where minority voters can elect
85
candidates of choice, key component of Voting Rights Act analysis.
86
87
Parameters:
88
- proposal (ProposalFunction): Function to propose new partitions
89
- constraints (List[ConstraintFunction]): Validation constraints
90
- accept (AcceptanceFunction): Acceptance function
91
- initial_state (Partition): Starting partition
92
- minority_column (str): Column name for minority population data
93
- threshold (float): Threshold for minority opportunity (default 0.5)
94
95
Returns:
96
None
97
"""
98
99
def districts_info(self) -> Dict[DistrictId, Dict[str, Any]]:
100
"""
101
Get detailed information about minority opportunity districts.
102
103
Returns:
104
Dict[DistrictId, Dict[str, Any]]: District demographics and analysis
105
"""
106
```
107
108
Usage example:
109
```python
110
from gerrychain.optimization import Gingles
111
112
# Set up Gingles analysis for Black voting age population
113
gingles = Gingles(
114
proposal=recom,
115
constraints=constraints,
116
accept=always_accept,
117
initial_state=partition,
118
minority_column="BVAP",
119
threshold=0.4 # 40% threshold for opportunity
120
)
121
122
# Analyze minority representation
123
district_info = gingles.districts_info()
124
125
minority_opportunity_districts = 0
126
for district_id, info in district_info.items():
127
if info["minority_percentage"] >= 0.4:
128
minority_opportunity_districts += 1
129
print(f"District {district_id}: {info['minority_percentage']:.1%} minority VAP")
130
131
print(f"Total minority opportunity districts: {minority_opportunity_districts}")
132
```
133
134
### Advanced Optimization Patterns
135
136
Examples of custom optimization workflows and advanced techniques:
137
138
```python
139
from gerrychain.optimization import SingleMetricOptimizer
140
from gerrychain.metrics import mean_median, polsby_popper
141
import numpy as np
142
143
# Multi-objective optimization using weighted combination
144
def combined_metric(partition, weight_partisan=0.7, weight_compactness=0.3):
145
"""Combine partisan fairness and compactness metrics."""
146
# Partisan component (minimize bias)
147
partisan_score = abs(mean_median(partition["SEN18"]))
148
149
# Compactness component (maximize average compactness)
150
pp_scores = polsby_popper(partition)
151
compactness_score = 1.0 - np.mean(list(pp_scores.values())) # Convert to minimize
152
153
# Weighted combination
154
return weight_partisan * partisan_score + weight_compactness * compactness_score
155
156
# Optimization with custom metric
157
def multi_objective_optimize(initial_partition, steps=10000):
158
optimizer = SingleMetricOptimizer(
159
proposal=recom,
160
constraints=constraints,
161
accept=always_accept,
162
initial_state=initial_partition,
163
maximize=False # Minimize combined score
164
)
165
166
best_partition, best_score = optimizer.optimize()
167
return best_partition, best_score
168
169
# Sequential optimization
170
def sequential_optimize(initial_partition):
171
"""First optimize for fairness, then for compactness."""
172
173
# Step 1: Optimize for partisan fairness
174
def fairness_metric(p):
175
return abs(mean_median(p["SEN18"]))
176
177
fairness_optimizer = SingleMetricOptimizer(
178
proposal=recom,
179
constraints=constraints,
180
accept=always_accept,
181
initial_state=initial_partition,
182
maximize=False
183
)
184
185
fair_partition, fairness_score = fairness_optimizer.optimize()
186
print(f"Fairness optimization complete: {fairness_score:.4f}")
187
188
# Step 2: Optimize for compactness while maintaining fairness
189
def compactness_metric(p):
190
pp_scores = polsby_popper(p)
191
return np.mean(list(pp_scores.values()))
192
193
# Add fairness constraint to maintain previous result
194
def maintain_fairness(p):
195
return abs(mean_median(p["SEN18"])) <= fairness_score * 1.1 # 10% tolerance
196
197
enhanced_constraints = constraints + [maintain_fairness]
198
199
compactness_optimizer = SingleMetricOptimizer(
200
proposal=recom,
201
constraints=enhanced_constraints,
202
accept=always_accept,
203
initial_state=fair_partition,
204
maximize=True # Maximize compactness
205
)
206
207
final_partition, compactness_score = compactness_optimizer.optimize()
208
print(f"Compactness optimization complete: {compactness_score:.4f}")
209
210
return final_partition
211
212
# Ensemble-based optimization
213
def ensemble_optimize(initial_partition, num_runs=10):
214
"""Run multiple optimization runs and select best result."""
215
216
results = []
217
218
for run in range(num_runs):
219
optimizer = SingleMetricOptimizer(
220
proposal=recom,
221
constraints=constraints,
222
accept=always_accept,
223
initial_state=initial_partition,
224
maximize=False
225
)
226
227
partition, score = optimizer.optimize()
228
results.append((partition, score, run))
229
print(f"Run {run+1}/{num_runs}: Score = {score:.4f}")
230
231
# Select best result
232
best_partition, best_score, best_run = min(results, key=lambda x: x[1])
233
print(f"Best result from run {best_run+1}: {best_score:.4f}")
234
235
return best_partition, best_score
236
237
# Use optimization functions
238
# optimized_partition = sequential_optimize(initial_partition)
239
# best_partition, score = ensemble_optimize(initial_partition, num_runs=5)
240
```
241
242
## Types
243
244
```python { .api }
245
ProposalFunction = Callable[[Partition], Partition]
246
ConstraintFunction = Callable[[Partition], bool]
247
AcceptanceFunction = Callable[[Partition], bool]
248
MetricFunction = Callable[[Partition], float]
249
OptimizationResult = Tuple[Partition, float]
250
```