Approximating Pareto Frontiers in Stochastic Multi-Objective Optimization via Hashing and Randomization
Authors: Jinzhao Li, Nan Jiang, Yexiang Xue
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.
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 1−δ, obtains γ-approximate Pareto frontiers (γ>1) 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 x and latent variables y1,y2 . 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 x collectively form an approximate Pareto frontier.
Figure 3: Converting a weighted function f(x,y) into unweighted model counting ∑zf^(x,y,z;b) . (Left) The function f is normalized and uniformly discretized into 2b integer levels, where b∈Z>0 is a user-specified discretization precision. The red bar shows an example f(x0,y0) , which is discretized to the binary integer (1,0,0,0)2 (or 8 in decimal). (Right) We construct an unweighted function f^ such that, when z∈{0,1}b is interpreted as a binary integer, f^(x,y,z;b)=1 if z is no greater than the discretized f(x,y) , and 0 otherwise. Then f(x,y) can be directly computed as ∑zf^ , e.g., the red bar shows that ∑zf^(x0,y0,z;b)=(1,0,0,0)2 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 S and the target node T under seasonal disruptions.
Radius
Solver
GD ↓
IGD ↓
HV ↑
SP ↓
500m
XOR-SMOO
<10−6
0.009 ± 0.004
0.796 ± 0.007
0.024 ± 0.005
NSGA2
<10−6
0.142 ± 0.037
0.772 ± 0.014
0.078 ± 0.053
AGE-MOEA
<10−6
0.099 ± 0.050
0.787 ± 0.009
0.155 ± 0.025
C-TAEA
<10−6
0.051 ± 0.004
0.773 ± 0.008
0.121 ± 0.031
RVEA
<10−6
0.177 ± 0.005
0.733 ± 0.008
0.027 ± 0.010
SMS-EMOA
<10−6
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.
Many-objective optimisation, a subset of multi-objective optimisation, involves optimisation problems with more than three objectives. As the number of objectives increases, the number of solutions needed to adequately represent the entire Pareto front typically grows substantially. This makes it challenging, if not infeasible, to design a search algorithm capable of effectively exploring the entire Pareto front. This difficulty is particularly acute in the Bayesian optimisation paradigm, where sample efficiency is critical and only a limited number of solutions (often a few hundred) are evaluated. Moreover, after the optimisation process, the decision-maker eventually selects just one solution for deployment, regardless of how many high-quality, diverse solutions are available. In light of this, we argue an idea that under a very limited evaluation budget, it may be more useful to focus on finding a single solution of the highest possible quality for the decision-maker, rather than aiming to approximate the entire Pareto front as existing many-/multi-objective Bayesian optimisation methods typically do. Bearing this idea in mind, this paper proposes a single point-based multi-objective search framework (SPMO) that aims to improve the quality of solutions along a direction that leads to a good tradeoff between objectives. Within SPMO, we present a simple acquisition function, called expected single-point improvement (ESPI), working under both noiseless and noisy scenarios. We show that ESPI can be optimised effectively with gradient-based methods via the sample average approximation (SAA) approach and theoretically prove its convergence guarantees under the SAA. We also empirically demonstrate that the proposed SPMO is computationally tractable and outperforms state-of-the-arts on a wide range of benchmark and real-world problems.
Chao Jiang, Jingyu Huang, Miqing Li
School of Computer Science, University of Birmingham · School of Mathematics, University of Birmingham
Pareto optimization via evolutionary multi-objective algorithms has been shown to efficiently solve constrained monotone submodular functions. Traditionally when solving multiple problems, the algorithm is run for each problem separately. We introduce multitasking formulations of these problems that are an effective way to solve multiple related problems with a single run. In our setting the given problems share a monotone submodular function f but have different knapsack constraints. We examine the case where elements within a constraint have the same cost and show that our multitasking formulations result in small Pareto fronts. This allows the population to share solutions between all problems leading to significant improvements compared to running several classical approaches independently. Using rigorous runtime analysis, we analyze the expected time until the introduced multitasking approaches obtain a (1−1/e)-approximation for each of the given problems. Our experimental investigations for the maximum coverage problem give further insight into the dynamics behind how the approach works and doesn't work in practice for problems where elements within a constraint also have varied costs.
Liam Wigney, Frank Neumann
Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia
Multi-objective optimization (MOO) has received growing attention in applications that require learning under multiple criteria. However, most existing MOO formulations do not explicitly account for distributional shifts in the data. We introduce distributionally robust multi-objective optimization (DR-MOO), which minimizes multiple objectives under their respective worst-case distributions. We propose Pareto-type solution concepts for DR-MOO and develop multi-gradient descent algorithms (MGDA) with provable guarantees. Leveraging a Lagrangian dual reformulation, we first design a double-loop MGDA that uses an inner loop to estimate dual variables and achieves a total sample complexity O(ε−8) for reaching an ε-Pareto-stationary point. To further improve convergence, we combine large-batch sampling with gradient clipping to accommodate generalized smoothness and control bias in stochastic preference updates, eliminating the need for double sampling. This yields a single-loop double-clip MGDA with substantially improved sample complexity O(ε−4). Our theory applies to nonconvex problems without requiring uniformly bounded gradients of the dual objectives. Experiments demonstrate that our methods are competitive with state-of-the-art MGDA baselines.
Yufeng Yang, Fangning Zhuo, Ziyi Chen +2
Texas A&M University · A*STAR · University of Maryland