cs.LGApr 1, 2026
SaveApproximating Pareto Frontiers in Stochastic Multi-Objective Optimization via Hashing and Randomization
Organizations: Department of Computer Science, Purdue University, 610 Purdue Mall, West Lafayette, 47907, IN, United States. · Department of Computer Science, University of Texas at El Paso, 500 W University Ave, El Paso, 79968, TX, United States.
Abstract
Stochastic Multi-Objective Optimization (SMOO) is critical for decision-making trading off multiple potentially conflicting objectives in uncertain environments. SMOO aims at identifying the Pareto frontier, which contains all mutually non-dominating decisions. The problem is highly intractable due to the embedded probabilistic inference, such as computing the marginal, posterior probabilities, or expectations. Existing methods, such as scalarization, sample average approximation, and evolutionary algorithms, either offer arbitrarily loose approximations or may incur prohibitive computational costs. We propose XOR-SMOO, a novel algorithm that with probability , obtains -approximate Pareto frontiers () for SMOO by querying an SAT oracle poly-log times in and . A -approximate Pareto frontier is only below the true frontier by a fixed, multiplicative factor . Thus, XOR-SMOO solves highly intractable SMOO problems (#P-hard) with only queries to SAT oracles while obtaining tight, constant factor approximation guarantees. Experiments on real-world road network strengthening and supply chain design problems demonstrate that XOR-SMOO outperforms several baselines in identifying Pareto frontiers that have higher objective values, better coverage of the optimal solutions, and the solutions found are more evenly distributed. Overall, XOR-SMOO significantly enhanced the practicality and reliability of SMOO solvers.
Figures & tables
Figure 1: Solving SMOO problems via querying satisfiability oracles. ( Left ) In multi-objective optimization (MOO), Papadimitriou et al. [ 9 ] lays down a multiplicative grid, where adjacent grid points are separated by . Then, for every grid point, a SAT oracle is queried to determine if a solution exists such that each of its objective value exceeds the grid point’s value at the corresponding dimension. SAT oracles’ responses split the entire region into a ( SAT ) and a ( UNSAT ) region. The top of all green points form a -approximate Pareto frontier. ( Right ) In SMOO, with high probability, our developed probabilistic oracle makes the correct SAT/UNSAT decisions only when the objective values exceed (or lack behind) the queried threshold by a fixed multiplicative constant. This brings in a third, intermediate uncertain region (shown in blue ). However, because its width can be controlled, the top of all green points still form a -approximate Pareto frontier.
Figure 2: Illustration of our approach for solving SMOO problems in a two-objective maximization setting. Task: Both objectives involve model counting, are defined over decision variables and latent variables . The orange curve shows the Pareto frontier. Step 1: By discretizing objective space multiplicatively by a factor of 2, optimization is converted into a set of SAT queries asking whether the thresholds at each grid point are jointly achievable, separating points into SAT (green) and UNSAT (red) regions. The true Pareto frontier is sandwiched between the adjacent green/red points. Step 2: Since each SAT query is intractable, we instead use a probabilistic SAT oracle providing two guarantees: (1) correctness of the SAT/UNSAT outcome; and (2) if SAT, the returned solution achieves tightly guaranteed objective values. These guarantees yield a sketch of the Pareto frontier via the SAT/UNSAT boundary, and the corresponding solutions collectively form an approximate Pareto frontier.
Figure 3: Converting a weighted function into unweighted model counting . (Left) The function is normalized and uniformly discretized into integer levels, where is a user-specified discretization precision. The red bar shows an example , which is discretized to the binary integer (or in decimal). (Right) We construct an unweighted function such that, when is interpreted as a binary integer, if is no greater than the discretized , and otherwise. Then can be directly computed as , e.g., the red bar shows that exactly.
Figure 4: Road Network Strengthening to Mitigate Seasonal Disruptions. Green edges denote operational road segments, while red edges represent disrupted segments under seasonal events. Yellow and blue regions indicate high-impact disruption areas in summer (e.g., heavy rain, extreme heat) and winter (e.g., heavy snow, extreme cold), respectively. The planner selects a limited set of road segments to strengthen in order to maintain connectivity between the source node and the target node under seasonal disruptions.
| Radius | Solver | GD | IGD | HV | SP |
|---|---|---|---|---|---|
| 500m | XOR-SMOO | 0.009 0.004 | 0.796 0.007 | 0.024 0.005 | |
| NSGA2 | 0.142 0.037 | 0.772 0.014 | 0.078 0.053 | ||
| AGE-MOEA | 0.099 0.050 | 0.787 0.009 | 0.155 0.025 | ||
| C-TAEA | 0.051 0.004 | 0.773 0.008 | 0.121 0.031 | ||
| RVEA | 0.177 0.005 | 0.733 0.008 | 0.027 0.010 | ||
| SMS-EMOA | 0.171 0.022 | 0.716 0.031 | 0.077 0.016 |
Table 1: Pareto frontier quality metrics for the Road Network Strengthening under Seasonal Disruptions scenario. Lower GD, IGD, and SP indicate better performance ( ), while higher HV indicates better performance ( ). All reported values are given as mean standard deviation over five independent runs, each conducted under a one-hour time limit. Cell colors denote ranking: deep blue indicates the best performance, and light blue indicates the second best. Across all radii (500m, 1000m, 1500m), XOR-SMOO consistently achieves the lowest (or tied-lowest) GD, indicating that its solutions are closest to the reference Pareto frontier and thus exhibit the best solution quality. It also attains the lowest IGD and highest HV scores, demonstrating superior coverage of the frontier, strong approximation across all regions of the Pareto set, and successful discovery of corner trade-off solutions. Finally, its low SP values indicate a more evenly-distributed solutions along the frontier, reflecting better diversity and stability.
Figure 5: Pareto frontier curves for the Road Network Strengthening under Seasonal Disruptions scenario. Both objectives are maximized; therefore, solutions closer to the upper-right corner represent better trade-offs. Overall, XOR-SMOO consistently identifies higher-quality solutions and recovers a broader Pareto frontier, achieving better solution quality and Pareto frontier coverage compared to baseline methods.
| Radius | Solver | GD | IGD | HV | SP |
|---|---|---|---|---|---|
| Burma7 | XOR-SMOO | 0.0057 0.0009 | 0.0174 0.0054 | 0.2478 0.0026 | 0.0423 0.0058 |
| NSGA2 | 0.0278 0.0028 | 0.0497 0.0092 | 0.2148 0.0109 | 0.0462 0.0032 | |
| AGE-MOEA | 0.0214 0.0033 | 0.0603 0.0044 | 0.2091 0.0022 | 0.0493 0.0026 | |
| C-TAEA | 0.0059 0.0026 | 0.0884 0.0129 | 0.1747 0.0146 | 0.0573 0.0059 | |
| RVEA | 0.0172 0.0024 | 0.0769 0.0009 | 0.1881 0.0021 | 0.0858 0.0012 | |
| SMS-EMOA | 0.0191 0.0013 | 0.0667 0.0032 | 0.1921 0.0033 | 0.0556 0.0162 |
Table 2: Pareto frontier quality metrics for the Flexible Supply Chain Network Design problem. Lower GD, IGD, and SP indicate better performance ( ), while higher HV indicates better performance ( ). Values are mean standard deviation over five independent runs, with each run limited to one hour. Cell colors denote ranking: deep blue indicates best and light blue indicates second best. Results are reported for three TSPLIB instances (Burma7, Burma14, and Ulysses16), where the number denotes the number of transfer hubs. Across all instances, XOR-SMOO achieves the lowest GD, indicating better solutions, and consistently superior IGD and HV, meaning better coverage of the Pareto frontier. Its competitive SP values further demonstrate more evenly distributed solutions. Noted that as the number of hubs increases, the flexibility objective becomes more challenging due to the exponential growth of feasible shipment patterns, and the performance gap between XOR-SMOO and baselines widens.
Figure 6: Pareto frontier curves for the Transportation Network Design problem. The flexibility objective is maximized while total length is minimized; therefore, solutions closer to the upper-left corner represent better trade-offs. Overall, XOR-SMOO consistently identifies higher-quality solutions and recovers a broader Pareto frontier, achieving superior convergence and coverage compared to baseline methods. As the number of transfer hubs increases, the combinatorial flexibility objective becomes more challenging, and the performance gap between XOR-SMOO and other SOTA methods widens, further highlighting the advantage of our approach.