Black-Box Optimization with Implicit Constraints for Public Policy

Wenqian Xing, Jungho Lee, Chong Liu, Shixiang Zhu

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.

Introduction: The Challenge of Implicit Constraints

In public policy, decision-making often involves "black-box" optimization where the objective function lacks an analytical form and must be evaluated through complex simulations. A primary example is police redistricting, where the goal is to balance workloads across zones. Standard optimization tools struggle in this domain due to two major hurdles: high dimensionality and implicit constraints.

Implicit constraints are rules that are socio-political or geographical in nature. While an expert can easily verify if a map is feasible (e.g., ensuring it doesn't bisect a major neighborhood or cut off highway access), these rules are nearly impossible to formalize as mathematical equations. Consequently, the search space is riddled with "infeasible" regions that traditional algorithms waste time exploring.

Examples of feasible (Pre-2019, Post-2019) and infeasible redistricting plans in the context of police zone design.

The CageBO Framework

To bridge the gap between expert intuition and algorithmic search, we introduce CageBO (Conditional and Generative Black-box Optimization). This framework treats constraint satisfaction as a generative modeling task, learning the "shape" of feasible solutions from labeled data.

1. Learning the Feasible Manifold

CageBO utilizes a Conditional Variational Autoencoder (CVAE) to learn the distribution of feasible decisions. By training on a dataset of labeled examples (feasible vs. infeasible), the CVAE creates a two-way mapping between the messy, high-dimensional decision space ($\mathcal{X}$) and a lower-dimensional, constraint-free latent space ($\hat{\mathcal{Z}}$). This latent space effectively compresses the search area to only include solutions that "look" feasible to the model.

2. Latent Space Optimization

Optimization occurs within this simplified latent space. CageBO employs a Gaussian Process (GP) as a surrogate model to approximate the objective function. It uses the Lower Confidence Bound (LCB) acquisition function to navigate the exploitation-exploration trade-off, selecting the next point in the latent space to test.

The CageBO framework: mapping the decision space to a feasible latent space via CVAE and performing optimization.

3. Post-Decoding Projection

Because the CVAE is a probabilistic model, it may occasionally decode a latent point into an infeasible decision. To maintain efficiency, CageBO includes a post-decoding projection step. If a generated policy fails the feasibility check (the "oracle"), it is projected to the nearest known feasible point in the training set, ensuring the algorithm remains within the valid manifold.

Experimental Evaluation

We validated CageBO across three distinct environments:

  • Synthetic Benchmarks: 30-dimensional versions of Keane’s bump and Michalewicz functions, serving as stress tests for constrained optimization.
  • Synthetic Grid Redistricting: A 6x6 grid divided into 4 zones to test workload balancing capabilities.
  • Atlanta Police Department (APD) Case Study: A real-world application involving 78 service regions in Atlanta, Georgia, divided into 6 zones. This study utilized historical 911 call data from 2021-2022 to estimate workloads and travel times.

Key Results

CageBO demonstrated superior convergence and efficiency compared to baselines like Simulated Annealing (SA) and standard VAE-guided Bayesian Optimization. In the APD case study, CageBO found districting plans with significantly lower workload variance in far fewer iterations. Furthermore, we provide a theoretical "no-regret" bound, mathematically guaranteeing that CageBO will eventually converge to the global optimum.

Conclusion and Future Work

CageBO offers a robust solution for high-dimensional policy problems with implicit constraints by leveraging generative modeling to simplify the search space. However, its performance is tied to the diversity of the initial labeled dataset. Future work will focus on integrating explicit fairness constraints to mitigate biases inherent in historical data (such as 911 call patterns) and adapting the framework for dynamic environments where policy constraints may shift over time.

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