Approximating Pareto frontiers in stochastic multi-objective optimization via hashing and randomization

Abstract Stochastic Multi-Objective Optimization (SMOO) is critical for decision-making that trades off multiple potentially conflicting objectives in uncertain environments. SMOO aims to identify the Pareto frontier, which contains all mutually non-dominating decisions. The problem is highly intractable due to the embedded probabilistic inference, such as computing marginal probabilities, posterior probabilities, or expectations. Existing methods, such as scalarization, sample average approximation, and evolutionary algorithms, either offer arbitrarily loose approximations or incur prohibitive computational costs. We propose XOR-SMOO, a novel algorithm that, with probability $$\varvec{1-\delta }$$ , obtains $$\varvec{\gamma }$$ -approximate Pareto frontiers ( $$\varvec{\gamma>1}$$ ) for SMOO by querying a SAT oracle poly-log times in $$\varvec{\gamma }$$ and $$\varvec{\delta }$$ . A $$\varvec{\gamma }$$ -approximate Pareto frontier is only below the true frontier by a fixed, multiplicative factor $$\varvec{\gamma }$$ . 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 challenging road network strengthening, supply chain design, and regional access under rare disruptions demonstrate that XOR-SMOO outperforms state-of-the-art evolutionary-based multi-objective optimizers with exact and approximate objective function evaluators in identifying Pareto frontiers that have higher objective values and better coverage of the optimal solutions, and whose solutions are more evenly distributed. Overall, XOR-SMOO significantly enhanced the practicality and reliability of SMOO solvers.