Leveraging 0–1 linear programming for partitioning and sampling in simulation-based optimization: The case of nested partitions

Discrete Simulation-based Optimization (DSO) problems typically involve highly complex stochastic systems such as urban road networks or electric grid networks. For such problems, computing the value of the objective function requires computationally intensive simulations. Many solution methods rely on iteratively sampling and partitioning the feasible space to progressively concentrate the sampling effort on its most promising portions. To boost the effectiveness of such methods, it is fundamental to quickly identify which portions of the feasible space are relevant to explore through an effective partitioning scheme. In this paper, we focus on binary DSO problems and introduce Nested Clusters, an enhancement of Nested Partitions that leverages the mathematical formulation of the feasible space to construct auxiliary 0–1 linear programming formulations for partitioning and sampling. Additionally, we expand Nested Clusters by introducing a biasing technique that improves the average quality of the sampled solutions, boosting the overall performance. Finally, we apply Nested Clusters to a simulation-based charger location problem for an autonomous fleet of ride-hailing taxis in New York City, which serves as our primary benchmark. We conduct further controlled synthetic tests on four binary simulation–optimization problems spanning different combinatorial structures and stochastic evaluators. On the tested ride-hailing charger-location instances, both proposed partitioning and biased sampling strategies independently improve solution quality relative to Nested Partitions; combining them yields an average 2.2% improvement in the best solutions found.