Computing Diverse Sets of Solutions for Monotone Submodular Optimisation Problems

Aneta Neumann, Jakob Bossek, Frank NeumannarXiv 2020 · OpenReview

Abstract

Submodular functions allow to model many real-world optimisation problems. This paper introduces approaches for computing diverse sets of high quality solutions for submodular optimisation problems. We first present diversifying greedy sampling approaches and analyse them with respect to the diversity measured by entropy and the approximation quality of the obtained solutions. Afterwards, we introduce an evolutionary diversity optimisation approach to further improve diversity of the set of solutions. We carry out experimental investigations on popular submodular benchmark functions that show that the combined approaches achieve high quality solutions of large diversity.

Introduction

In classical optimization, the objective is typically to identify a single optimal solution. However, real-world applications—such as sensor network planning, social network influence maximization, or portfolio selection—often require a set of diverse, high-quality options. This diversity allows decision-makers to account for secondary constraints or unquantified preferences. This paper addresses this need within the context of monotone submodular optimization, where functions exhibit diminishing returns. While standard greedy algorithms provide efficient approximations, they are deterministic and produce only a single solution. We propose a hybrid framework that leverages greedy heuristics to ensure quality and evolutionary algorithms to maximize diversity.

Methodology

The proposed framework consists of two main components:

1. Diversifying Greedy Sampling (DGS)

Standard greedy algorithms iteratively select the element with the highest marginal gain until the budget $B$ is reached. DGS modifies this by stopping $m$ steps early (at $B - m$). To generate a population of $\mu$ solutions, the algorithm randomly samples the remaining $m$ elements for each individual. This ensures that all solutions share a high-quality "core" while introducing initial variation. A generalized version (GDGS) is also provided for knapsack constraints, using cost-to-benefit ratios.

2. Entropy-Based Evolutionary Diversity Optimisation (DIVEA)

While DGS provides a baseline, the shared core elements limit the total population diversity. DIVEA addresses this by using the DGS output as an initial population. It defines a hard quality threshold ($f_{min}$) based on the worst-performing initial solution. The algorithm then applies random bit-flip mutations. Offspring are accepted if they satisfy the budget and the quality threshold. To maintain a fixed population size, individuals are removed based on their contribution to the overall population entropy, thereby iteratively "polishing" the set to maximize structural diversity.

Experimental Results

The algorithms were evaluated on two benchmark problems: Influence Maximization (IM) and Maximum Coverage (MC), using the frb30-15-01 social network graph (450 nodes, 17,827 edges).

Performance and Diversity

Theoretical results show that DGS maintains an approximation ratio close to the standard $(1 - 1/e)$ bound, with the quality drop strictly controlled by the margin $m$. Empirically, the transition from greedy sampling to evolutionary optimization results in massive entropy gains. For example, in a uniform constraint setting with $B=10$ and $m=2$, the initial DGS population achieved an entropy of approximately 4.6. After DIVEA optimization, this value increased to over 23.2 with no loss in the guaranteed quality threshold.

Table 1: Experimental results for submodular optimization under uniform constraints, showing the significant entropy increase from DGS (2) to DIVEA (3).

Consistency Across Constraints

The effectiveness of the DIVEA approach is not limited to uniform costs. In experiments involving knapsack constraints, the evolutionary step consistently outperformed greedy sampling in generating diverse sets across larger budgets.

Table 2: Results for Influence Maximization under knapsack constraints ($B=100$), demonstrating the scalability and consistency of the diversity optimization approach.

Key Insights and Conclusion

The study highlights a fundamental trade-off: by sacrificing a small, bounded amount of quality (via the margin $m$), one can unlock a significantly larger space of diverse solutions. While DGS serves as an efficient starting point, its deterministic nature creates a diversity bottleneck. Evolutionary algorithms like DIVEA are highly effective at breaking this bottleneck by iteratively swapping redundant elements for unique ones that maintain the required quality. Future work will explore more advanced evolutionary operators and investigate the scalability of these approaches for massive-scale submodular optimization tasks.

Summary updated

Abstract

Submodular functions allow to model many real-world optimisation problems. This paper introduces approaches for computing diverse sets of high quality solutions for submodular optimisation problems. We first present diversifying greedy sampling approaches and analyse them with respect to the diversity measured by entropy and the approximation quality of the obtained solutions. Afterwards, we introduce an evolutionary diversity optimisation approach to further improve diversity of the set of solutions. We carry out experimental investigations on popular submodular benchmark functions that show that the combined approaches achieve high quality solutions of large diversity.
BibTeX
@misc{neumann2020computing,
  author = {Aneta Neumann and Jakob Bossek and Frank Neumann},
  title = {{Computing Diverse Sets of Solutions for Monotone Submodular Optimisation Problems}},
  year = {2020},
  eprint = {2010.11486},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.11486},
}
Figure