Smoothed Analysis of Pareto Curves in Multiobjective Optimization

Heiko RöglinBeyond the Worst-Case Analysis of Algorithms 2020 · DOI · DBLP

Abstract: In a multiobjective optimization problem a solution is called Pareto-optimal if no criterion can be improved without deteriorating at least one of the other criteria. Computing the set of all Pareto-optimal solutions is a common task in multiobjective optimization to filter out unreasonable trade-offs. For most problems the number of Pareto-optimal solutions increases only moderately with the input size in applications. However, for virtually every multiobjective optimization problem there exist worst-case instances with an exponential number of Pareto-optimal solutions. In order to explain this discrepancy, we analyze a large class of multiobjective optimization problems in the model of smoothed analysis and prove a polynomial bound on the expected number of Pareto-optimal solutions. We also present algorithms for computing the set of Pareto-optimal solutions for different optimization problems and discuss related results on the smoothed complexity of optimization problems.

Introduction

In multiobjective optimization, the goal is to identify Pareto-optimal solutions—trade-offs where improving one criterion (e.g., cost) necessarily degrades another (e.g., performance). The collection of these solutions forms the "Pareto curve." While theoretically, the number of Pareto-optimal solutions can grow exponentially with input size, practitioners often observe only a polynomial number of such solutions in real-world instances. This paper bridges this gap using smoothed analysis, providing a theoretical foundation for the observed efficiency of multiobjective algorithms.

Methodology: Smoothed Analysis

Smoothed analysis evaluates algorithm performance on inputs subjected to slight random perturbations. This approach avoids the pitfalls of worst-case analysis, which often focuses on highly improbable, hand-crafted pathological instances. By adding a small amount of noise (parameterized by $\phi$) to the input coefficients, we can determine the expected complexity of the problem.

Algorithmic Case Studies

The paper focuses on two fundamental problems:

  1. The Knapsack Problem: This is analyzed using the Nemhauser-Ullmann algorithm. This iterative approach constructs the Pareto set by adding items one by one. Each step involves shifting the current Pareto curve by the weight and profit of the new item and then merging it with the previous curve.
Illustration of one iteration of the Nemhauser-Ullmann algorithm. The left panel shows the original Pareto curve $\mathcal{P}_{i-1}$ (blue) and its shifted version $\mathcal{P}_{i-1}^{+i}$ (red) after adding item $i$. The right panel shows the resulting merged curve $\mathcal{P}_i$ (green) after removing dominated solutions (marked with crosses).
  1. The Shortest Path Problem: The paper adapts the classic Bellman-Ford algorithm for bicriteria optimization. Instead of maintaining a single minimum distance, each node maintains a set of Pareto-optimal paths (e.g., minimizing both time and cost).
The standard Bellman-Ford algorithm. In multiobjective contexts, the RELAX procedure is modified to merge Pareto sets rather than comparing single scalar values.

Theoretical Insights

The core proof relies on a "winner-loser" analysis. For any weight threshold $t$, the "winner" is the most valuable solution within that weight. A "loser" is a solution with higher value but also higher weight. A Pareto-optimal solution only exists in a very narrow weight interval if the "loser" is only marginally heavier than the "winner." Under random perturbations, such "close calls" are statistically rare, leading to a polynomial expected number of Pareto points.

A key distinction is made between weakly NP-hard problems (like Knapsack), which become tractable under smoothed analysis, and strongly NP-hard problems (like the Traveling Salesman Problem), which remain difficult even with noise.

Key Results

The analysis yields several significant bounds on the expected number of Pareto-optimal solutions:

  • Knapsack: For $n$ items with weights perturbed by $\phi$, the expected number of solutions is $O(n^2\phi)$. The Nemhauser-Ullmann algorithm runs in expected $O(n^3\phi)$ time.
  • Shortest Paths: For a graph with $m$ edges, the expected number of Pareto-optimal paths is $O(m^2\phi)$.
  • Universality: These polynomial bounds are robust and apply to a wide class of problems where at least one objective has linear, perturbed coefficients.

Conclusion and Future Work

Smoothed analysis successfully explains why multiobjective optimization is often efficient in practice despite exponential worst-case bounds. Future research directions include modeling correlated objectives, which are common in reality and may lead to even smaller Pareto sets. Additionally, extending these results to higher dimensions ($d > 2$ objectives) and developing output-sensitive algorithms for problems like the multiobjective spanning tree remain active areas of inquiry.

Summary updated

BibTeX
@inproceedings{roglin2020smoothed,
  author = {Heiko Röglin},
  title = {{Smoothed Analysis of Pareto Curves in Multiobjective Optimization}},
  booktitle = {Beyond the Worst-Case Analysis of Algorithms},
  year = {2020},
  doi = {10.1017/9781108637435.020},
}
Figure