(125e) Decision-Aware Scenario Reduction Via Partial Optimal Transport for Efficient Stochastic Optimization

Stochastic optimization is a framework for modeling decision-making under uncertainty, where the objective is to find a decision that minimizes the expected cost over a distribution of uncertain parameters. In practice, the underlying probability distribution is often approximated by a finite empirical distribution derived from sampled scenarios. However, solving stochastic optimization problems with a large number of scenarios can be computationally prohibitive. Various scenario reduction methods have been proposed [1,2,3]. However, few of them consider the decision quality while applied to the stochastic optimization problems [4]. To address this challenge, we propose a decision-aware scenario reduction framework based on partial optimal transport theory that balances computational tractability with solution fidelity.

Our approach formulates scenario reduction as a constrained optimization problem in which a reduced distribution is constructed by reweighting a subset of scenarios from the original empirical distribution while discarding the rest. To control the fraction of information retained, we introduce a dummy scenario that absorbs the discarded mass, parameterized by a user-defined retention ratio. The reduced distribution is supported on the original scenarios, and the optimal transport from the full to the reduced distribution is constrained to have zero cost under the Wasserstein metric, ensuring that probability mass can only be transferred from a scenario to itself or to the dummy point. This enforces strict subset selection and prevents mixing between distinct scenarios. One advantage of this proposed method is that it does not use integer variables in the final optimization model.

We propose decision-aware scenario reduction frameworks through incorporating the impact of scenario reduction on the stochastic optimization task. Two frameworks for decision-aware scenario reduction are proposed: 1) In the first framework, we precompute optimal values from single-scenario deterministic subproblems and define a cost matrix over these outcomes. A classical optimal transport problem is then formulated to minimize the Wasserstein distance between the full and reduced distributions of objective values, ensuring the decision quality is preserved post-reduction. The stochastic optimization problem can be implemented based on the reduced scenarios subsequently. 2) In the second framework, we jointly optimize both the scenario reduction and the stochastic optimization objective, instead of solving each scenario-specific subproblem in advance. This is achieved by formulating a composite objective that combines the scenario reduction loss and the stochastic optimization cost, weighted appropriately. We develop an efficient iterative algorithm that alternates between updating the reduced distribution and solving the stochastic optimization problem

We demonstrate the effectiveness of the proposed method using stochastic supply chain optimization problems. The results show that the reduced scenario set maintains high fidelity to the original optimization outcomes, as evidenced by the preservation of both the scenario distribution and the distribution of optimal values. The proposed framework bridges the gap between data-driven scenario generation and decision-aware learning, offering an effective tool for solving stochastic optimization models.

References:

[1] Heitsch, H., & Römisch, W. Scenario reduction algorithms in stochastic programming. Computational optimization and applications, 2003, 24, 187-206.

[2] S. Kammammettu, Z. Li. Scenario Reduction and Scenario Tree Generation for Stochastic Programming using Sinkhorn Distance. Computers & Chemical Engineering. 2023, 170, 108122.

[3] Zhuangzhi Li, Z. Li. Linear Programming based Scenario Reduction using Transportation Distance. Computers & Chemical Engineering. 2016, 88, 50-58.

[4] Z. Li, C.A. Floudas. Optimal scenario reduction framework based on distance of uncertainty distribution and output performance: I. Single reduction via mixed integer linear optimization. Computers & Chemical Engineering. 2014, 70, 50-66.