Black-Box Optimization with Implicit Constraints for Public Policy

Wenqian Xing, Jungho Lee, Chong Liu, Shixiang Zhu

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:

  1. 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.
  2. 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:

The CageBO framework mapping decision space to a feasible latent space.
  1. 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.
  2. 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.
  3. 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.

Comparison of feasible (Pre/Post-2019) and infeasible redistricting plans for Atlanta.

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

Abstract

Black-box optimization (BBO) has become increasingly relevant for tackling complex decision-making problems, especially in public policy domains such as police redistricting. However, its broader application in public policymaking is hindered by the complexity of defining feasible regions and the high-dimensionality of decisions. This paper introduces a novel BBO framework, termed as the Conditional And Generative Black-box Optimization (CageBO). This approach leverages a conditional variational autoencoder to learn the distribution of feasible decisions, enabling a two-way mapping between the original decision space and a simplified, constraint-free latent space. The CageBO efficiently handles the implicit constraints often found in public policy applications, allowing for optimization in the latent space while evaluating objectives in the original space. We validate our method through a case study on large-scale police redistricting problems in Atlanta, Georgia. Our results reveal that our CageBO offers notable improvements in performance and efficiency compared to the baselines.
BibTeX
@inproceedings{xing2025black,
  author = {Wenqian Xing and Jungho Lee and Chong Liu and Shixiang Zhu},
  title = {{Black-Box Optimization with Implicit Constraints for Public Policy}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i27.35074},
}
Figure