Abstract
Designing public policy often involves optimizing complex systems subject to implicit constraints that are difficult to formalize mathematically. We present CageBO (Conditional And Generative Black-box Optimization), a framework that leverages generative modeling to learn the manifold of feasible policy decisions. By mapping high-dimensional, constrained search spaces into a lower-dimensional, constraint-free latent space, CageBO enables efficient Bayesian Optimization. We demonstrate its effectiveness on synthetic benchmarks and a real-world police redistricting case study in Atlanta, showing significant improvements in workload balancing over traditional methods.
Introduction
Public policy design, such as police redistricting, is frequently an optimization challenge characterized by "implicit constraints." While the primary goal might be to balance workloads across zones, proposed solutions must also satisfy unwritten rules regarding highway access, socio-economic boundaries, and geographic contiguity. These constraints are often easily identified by human experts but are analytically challenging to incorporate into standard optimization formulas. Consequently, traditional black-box optimization (BBO) methods struggle to find feasible, let alone optimal, solutions in these high-dimensional haystacks.
Problem Statement
Traditional BBO treats objective functions as unknown but assumes the search space is relatively accessible. In public policy, two hurdles complicate this:
- Implicit Constraints: Many rules are "unrelaxable" and lack analytical formulations. While a "feasibility oracle" (e.g., a simulator or human expert) can validate a plan, no explicit equation defines the feasible region.
- High Dimensionality: Problems like urban redistricting involve hundreds or thousands of decision variables, leading to the "curse of dimensionality" where standard BBO methods fail to converge.
The CageBO Framework
The CageBO algorithm addresses these challenges through a three-phase generative approach:
- Learning the Manifold: A Conditional Variational Autoencoder (CVAE) is trained on labeled decisions (feasible vs. infeasible). This model learns to compress the complex decision space into a lower-dimensional, "clean" latent space.
- Latent Space Optimization: Bayesian Optimization (BO) is performed within this latent space. A Gaussian Process (GP) serves as a surrogate model for the objective function, and an acquisition function (Lower Confidence Bound) identifies the next point to evaluate.
- Post-Decoding Refinement: To ensure decoded latent points remain feasible in the original space, a post-decoding process projects points to the nearest known feasible decision.
Experimental Evaluation
The authors validated CageBO using synthetic benchmarks (Keane’s bump and Michalewicz functions) and a real-world case study involving the Atlanta Police Department (APD). The APD study required dividing 78 service regions into 6 zones, utilizing historical 911 call data to calculate workload variance.
Results and Discussion
CageBO demonstrated superior convergence across all tests, reaching lower objective values faster than vanilla BO, Simulated Annealing, and other VAE-based methods. In the Atlanta case study, the algorithm successfully reduced workload variance while generating plans that aligned with human-centric heuristic policies. By reducing the dimensionality of the APD problem from 78 regions to a 25-dimensional latent space, CageBO effectively bypassed the computational bottlenecks typical of high-dimensional policy optimization.
Conclusion
CageBO offers a robust framework for optimizing public policy under implicit constraints by treating constraints as a learnable manifold rather than rigid boundaries. While the method requires initial labeled data and incurs some computational overhead for CVAE training, its ability to navigate complex, high-dimensional spaces makes it a powerful tool for modern governance. Future research may explore active learning techniques to further reduce the data requirements for the feasibility oracle.
Summary updated