A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization

Aharon Ben-Tal, Omar El Housni, Vineet GoyalMath. Program 2020 · DOI

TL;DR

This paper introduces a novel framework for designing "piecewise affine policies" to efficiently solve complex two-stage adjustable robust optimization problems. By approximating the uncertainty set with a simpler "dominating simplex," the authors develop a method that offers significant performance improvements over existing affine policies, especially for certain classes of uncertainty, and is computationally more efficient.

What Problem Does This Paper Address?

Real-world decision-making often involves uncertainty, and robust optimization provides a framework to handle this by considering the worst-case scenario. Two-stage adjustable robust optimization (AR) is a powerful model where decisions are made in two stages, with the second stage decision adapting to the realization of uncertainty. However, finding optimal AR policies can be computationally intractable, especially when the uncertainty set is complex or high-dimensional. Existing approaches like static policies (making a single decision for all uncertainties) or affine policies (where the second-stage decision is a linear function of uncertainty) offer tractability but can lead to suboptimal solutions or poor performance bounds. This paper tackles the challenge of finding a more effective and computationally feasible AR policy that can better adapt to uncertainty than affine policies.

Methods

The core of the paper's contribution lies in a new framework for constructing piecewise affine policies (PAP). Instead of directly partitioning the complex uncertainty set $U$, the authors propose approximating it with a simpler, "dominating" uncertainty set $\hat{U}$. This $\hat{U}$ is chosen such that it "dominates" $U$, meaning for every realization $h$ in $U$, there's a corresponding realization $\hat{h}$ in $\hat{U}$ that is "worse" (i.e., $\hat{h} \ge h$). Crucially, $\hat{U}$ is chosen to be a simplex, which has a small number of extreme points, making the AR problem over $\hat{U}$ efficiently solvable.

The piecewise affine policy is then constructed by mapping points from the original uncertainty set $U$ to the dominating simplex $\hat{U}$ using a piecewise affine function. This mapping allows the policy to leverage the efficient solution over $\hat{U}$ while still providing feasible and near-optimal solutions for the original problem over $U$. The authors develop specific techniques for constructing the dominating simplex $\hat{U}$ and the mapping function, particularly for scaled permutation invariant (SPI) sets and general uncertainty sets.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and computational experiments with synthetic uncertainty sets.

Key Insights and Ideas

  • Dominating Simplex Approximation: The key insight is that instead of directly handling a complex uncertainty set $U$, approximating it with a simpler dominating simplex $\hat{U}$ can lead to efficient computation and good performance. The "dominating" property is crucial for ensuring feasibility.
  • Piecewise Affine Mapping: The piecewise affine mapping from $U$ to $\hat{U}$ is the mechanism that translates the efficient solution over $\hat{U}$ into a policy for $U$. This allows for more flexibility than a simple affine policy.
  • Performance Gains for Specific Uncertainty Sets: The framework yields significant theoretical and empirical improvements over affine policies for certain classes of uncertainty, such as hyperspheres and norm balls. This highlights that the choice of uncertainty set structure is critical for policy performance.
  • Computational Efficiency: For many cases, the proposed piecewise affine policy is not only more accurate but also computationally faster than solving the affine policy, especially as the problem size ($m$) increases.

Key Results

  • Theoretical Bounds: The paper provides theoretical approximation bounds for the piecewise affine policy. For hypersphere uncertainty sets, the bound is $O(m^{1/4})$, a significant improvement over the affine policy's $O(\sqrt{m})$. For $p$-norm balls, the bound is $O(m^{p-1}/p)$, also outperforming affine policies.
  • General Uncertainty Sets: For general uncertainty sets, the framework provides an $O(\sqrt{m})$-approximation, matching the worst-case bound of affine policies, but the method is still computationally efficient.
  • Computational Experiments: Numerical results demonstrate that the piecewise affine policy consistently outperforms affine policies in terms of objective function value for hypersphere, norm-ball, and generalized budget uncertainty sets. The performance gap widens with increasing problem size ($m$).
  • Computational Time: The piecewise affine policy is significantly faster than affine policies for larger problem instances, with running times often less than a second, while affine policies can take minutes.

Limitations and Future Work

  • Not Always Optimal: The authors acknowledge that their piecewise affine policy is not necessarily an optimal policy. There are instances, particularly for budget uncertainty sets, where affine policies can perform better.
  • General Uncertainty Sets Complexity: While the framework handles general uncertainty sets, constructing the dominating simplex $\hat{U}$ can be computationally more challenging, requiring solving a sequence of Mixed-Integer Programs (MIPs). However, the parameters of $\hat{U}$ depend only on the uncertainty set, allowing for offline computation.
  • Future Work: The paper poses an open question about designing a piecewise affine policy that can significantly improve over affine policies for budgeted uncertainty sets. Further research could explore more sophisticated dominating sets or alternative mapping strategies.

Summary updated

BibTeX
@article{bental2020tractable,
  author = {Aharon Ben-Tal and Omar El Housni and Vineet Goyal},
  title = {{A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization}},
  journal = {Math. Program.},
  year = {2020},
  doi = {10.1007/s10107-019-01385-0},
}

Loading related content...

Figure