Source-linked AI summary
Approximating the least hypervolume contributor: NP-hard in general, but fast in practice
Karl Bringmann, Tobias Friedrich
TL;DR
Hypervolume-based optimizers often need to identify a least-contributing solution, but contribution calculation and least-contributor decisions are hard problems. The algorithm cannot run in polynomial time for all instances; its runtime depends on an input hardness measure H, generally unbounded in n and d. In 100 dimensions, the algorithm solved all tested problems with fewer than 6000 solutions within 100 seconds, while HSO and BR solved none with six solutions in that time.
Problem
Hypervolume-based optimizers often need to identify a least-contributing solution, but contribution calculation and least-contributor decisions are hard problems.
Source: New complexity results · p. 3Method
The algorithm cannot run in polynomial time for all instances; its runtime depends on an input hardness measure H, generally unbounded in n and d.
Source: New approximation algorithm · p. 4Results
In 100 dimensions, the algorithm solved all tested problems with fewer than 6000 solutions within 100 seconds, while HSO and BR solved none with six solutions in that time.
Source: §5 · p. 19Takeaways & Limitations
The algorithm performed very quickly on tested practical instances, including large, high-dimensional instances intractable for previous exact algorithms and heuristics.
Source: §5 · p. 19The algorithm cannot run in polynomial time for all instances because its runtime depends on an input hardness measure that is generally unbounded.
Source: New approximation algorithm · p. 4
Abstract
from arXiv · showhide
The hypervolume indicator is an increasingly popular set measure to compare the quality of two Pareto sets. The basic ingredient of most hypervolume indicator based optimization algorithms is the calculation of the hypervolume contribution of single solutions regarding a Pareto set. We show that exact calculation of the hypervolume contribution is #P-hard while its approximation is NP-hard. The same holds for the calculation of the minimal contribution. We also prove that it is NP-hard to decide whether a solution has the least hypervolume contribution. Even deciding whether the contribution of a solution is at most $(1+\eps)$ times the minimal contribution is NP-hard. This implies that it is neither possible to efficiently find the least contributing solution (unless $P = NP$) nor to approximate it (unless $NP = BPP$). Nevertheless, in the second part of the paper we present a fast approximation algorithm for this problem. We prove that for arbitrarily given $\eps,\delta>0$ it calculates a solution with contribution at most $(1+\eps)$ times the minimal contribution with probability at least $(1-\delta)$. Though it cannot run in polynomial time for all instances, it performs extremely fast on various benchmark datasets. The algorithm solves very large problem instances which are intractable for exact algorithms (e.g., 10000 solutions in 100 dimensions) within a few seconds.
1 Introduction
The paper examines how to identify solutions with minimal hypervolume contribution, a task relevant to hypervolume-based optimizers. It establishes hardness results for contribution calculations and least-contributor decisions, then presents an approximation algorithm that performs quickly on tested instances.
1 Introduction
- Multi-objective optimization seeks Pareto-optimal sets because objectives often conflict and the Pareto set can grow exponentially with problem size.The paper identifies the hypervolume indicator as a widely used strictly Pareto-compliant measure of Pareto-set quality.Source: §1 · pp. 1–2
New complexity results
- CON is #P-hard to calculate exactly and NP-hard to approximate, while MINCON is #P-hard and remains hard even when the least contributor is known.Most hypervolume-based optimizers need to find a least-contributing box rather than calculate the hypervolume itself.Source: New complexity results · p. 3
- Deciding whether a box is the least contributor is NP-hard, as is finding one whose contribution is at most (1 + ε) times the minimum.The paper states that this rules out efficient computation of the relaxed problem unless P = NP.Source: New complexity results · pp. 3–4
New approximation algorithm
- The approximation algorithm targets a box within (1 + ε) of the minimum contribution with probability at least 1 − δ, but its runtime is not polynomially bounded for all instances.Its runtime depends on an input hardness measure that is generally unbounded.Source: New approximation algorithm · p. 4
- On benchmark datasets, the algorithm is practically very fast even at d = 100, described as intractable for exact algorithms, solving instances with n = 10000 points within seconds.Source: New approximation algorithm · p. 4
2 Hardness of approximation
Section 2 establishes hardness for calculating and approximating minimal contribution, then uses reductions to show that selecting a near-least contributor is NP-hard.
2 Hardness of approximation
- The reduction from #MON-CNF makes the designated box B's contribution equal the number of satisfying assignments, linking MINCON hardness to a #P-hard counting problem.The construction uses one box per clause and a further box B.Source: §2 · pp. 4–5
- MINCON is #P-hard and NP-hard to approximate, even when its least-contributing box is already known.The same construction also makes computing CON(M, B) hard and uses integral coordinates.Source: §2 · pp. 4–5
- ε-LC is NP-hard for every constant ε; the reduction encodes MINCON as whether threshold box Cλ is the least contributor.The proof obtains an approximation of MINCON through O(log(b)) calls to ε-LC.Source: §2 · pp. 5–7
- An efficient ε-δ-LC algorithm would imply NP = BPP, and approximating contributions can be only O(log(b)) slower than solving ε-LC.This connection motivates approximating contributions of the boxes in the practical algorithm presented next.Source: §2 · p. 7
3 Practical approximation algorithm
The algorithm estimates each box’s contribution by sampling its uniquely dominated bounding box, then eliminates clearly larger contributors or returns a near-minimal one. Its correctness is probabilistic, and practical heuristics reduce work without making the worst-case runtime polynomial.
3.1 The algorithm A
- A samples each box’s uniquely dominated bounding box, estimates its contribution and uncertainty, then eliminates boxes clearly above the current minimum or stops at the approximation threshold.Sampling proceeds in rounds with successively smaller error bounds; the algorithm returns the box with the smallest estimated contribution when the stopping criterion is met.Source: §3.1 · pp. 7–9
3.2 Runtime
- For random test cases, the hardness measure H is roughly between n log(n/δ) and 10n log(n/δ).The difficult cases are loose bounding boxes relative to contribution or multiple equal or near-equal minimal contributions; the paper reports these rarely occur in random instances.Source: §3.2 · pp. 10–11
3.3 Correctness of our algorithm
- If the algorithm’s estimates stay within their assumed error bounds, its elimination and stopping rules return a box contributing at most (1 + ε) times the minimum.The probability that any assumption is wrong is at most δ.Source: §3.3 · pp. 11–12
- With probability at least 1 − δ, A returns a box whose contribution is at most (1 + ε) times the minimum.The guarantee follows from the algorithm’s correctness when its estimates satisfy their assumed error bounds and the probability bound on any failed assumption.Source: §3.3 · pp. 11–13
3.4.1 Push on ∆(g
- Prioritizing samples for the current estimated minimum can improve runtime by up to a factor of 4.The authors found α = 0.2 a reasonable practical value for this heuristic.Source: §3.4.1 · p. 13
3.4.2 Sampling heuristic:
- Checking only boxes that can dominate a sample, ordered by their dominated portion of the bounding box, speeds unsuccessful searches.Precomputing the influencing boxes uses O(n^2) space and improves runtime by one to two orders of magnitude; ordering yields an additional small constant-factor speedup on real instances.Source: §3.4.2 · p. 14
3.4.3 Exact calculation:
- For boxes with few influencing boxes, the algorithm can replace sampling with an exact contribution calculation using a classical hypervolume algorithm.It estimates exact-calculation work against sampling work and switches when the sampling operations exceed the estimated HSO runtime; this decision uses at most twice the operations of the optimal choice.Source: §3.4.3 · pp. 14–15
- The exact-calculation heuristic does not help at high dimensions, such as d > 20; performance at d = 100 comes from sampling.The exact algorithms become unusable at those dimensions.Source: §3.4.3 · p. 15
4 Experimental analysis
The experiments compare the approximation algorithm with exact methods on scalable synthetic datasets. Except for small fronts, it substantially outperformed the exact methods, though its runtime varied more.
4.1 Datasets
- The benchmark used five randomly sampled fronts similar to DTLZ, avoiding optimizer-specific point distributions and allowing scalability in points and dimensions.The datasets use uniform and Gaussian random variables.Source: §4.1 · p. 16
4.1.1 Linear dataset:
- The linear dataset lies in [0, 1]^d with coordinate sum 1, using absolute Gaussian draws normalized to form points..Source: §4.1.1 · p. 16
4.1.2 Spherical dataset:
- The spherical dataset samples points uniformly on the positive unit sphere using Gaussian random draws and the method of Muller.Source: §4.1.2 · p. 17
4.1.3 Concave dataset:
- The concave dataset uses a square-root coordinate constraint and generates its points from Gaussian random draws.Source: §4.1.3 · p. 17
4.1.4 Random dataset 1:
- Random dataset 1 starts with uniform points in [0, 1]^d and replaces dominated points until n nondominated points remain.Source: §4.1.4 · p. 17
4.1.5 Random dataset 2:
- Random dataset 2 similarly rejects dominated points but draws from a Gaussian distribution in the nonnegative orthant with mean 1.For n ≥ 100 and d ≤ 5, finding nondominated points becomes increasingly unlikely and computationally expensive.Source: §4.1.5 · p. 17
4.2 Comparison
- The comparison ran HSO and BR on each front and again with each point removed, using the contribution differences; plots show median runtimes over 100 runs.The plots use logarithmic scales and examine different dimensions by dataset.Source: §4.2 · pp. 17–18
- Beyond n = 10, the approximation algorithm substantially outperformed HSO and BR across solution counts and dimensions.Its empirical standard deviation and interquartile range were higher; on random dataset 1, the upper quartile reached five times the median.Source: Figure 3 · p. 16, Figure 4 · p. 16, §4.2 · p. 18
5 CONCLUSIONS
The conclusions combine hardness results with strong performance on tested instances, while noting that broader experiments are still needed. The authors also compare their results and parameterization with other contribution algorithms.
5 CONCLUSIONS
- The approximation algorithm had substantially higher runtime variability, with maximum-to-average runtime reaching 66 on random dataset 1.Its non-monotonicity near n = 10 for d = 10 was attributed to approximations of exact-algorithm runtimes.Source: §5 · p. 19
- For d = 100, the algorithm solved all tested problems with fewer than 6000 solutions within 100 seconds, while HSO and BR solved none at that size.For 7 solutions on the 100-dimensional linear front, HSO took 13 minutes, BR 7 hours, and the approximation algorithm 0.5 milliseconds.Source: §5 · p. 19
- Compared with Bader and Zitzler’s confidence-based approximation, the authors emphasize their own framework’s two user-chosen parameters, ε and δ.They did not establish a mapping between the two parameter sets.Source: §5 · p. 19
- Against the exact algorithm of Bradstreet et al., the authors report speedups over HSO above 1000 at n = 20 and d = 10, versus a maximum of 50 for that exact method.Source: §5 · p. 19
- The paper proves natural hypervolume-contribution questions hard to decide and approximate, yet reports fast performance on tested instances, including large high-dimensional cases.The algorithm handled instances with d ≥ 10 and n ≥ 100 that previous exact algorithms and heuristics could not handle.Source: §5 · p. 19
5 Conclusions
- The authors call for broader dataset comparisons and say their conjecture that close contribution values slow the algorithm needs further substantiation.Source: §5 · pp. 19–20