An efficient branch-and-bound algorithm for submodular function maximization

Naoya Uematsu, Shunji Umetani, Yoshinobu Kawahara

Introduction

Submodular function maximization is a fundamental problem in discrete optimization, with applications ranging from sensor placement and feature selection to active learning. A function is submodular if it exhibits the property of diminishing returns: the marginal benefit of adding an element to a set decreases as the size of the set increases.

While maximizing these functions under a cardinality constraint (selecting exactly $k$ items) is NP-hard, the standard approach in practice is the greedy algorithm. Although the greedy method is computationally efficient and provides a $(1 - 1/e)$ approximation guarantee, it often fails to reach the global optimum. For high-stakes applications—such as critical infrastructure placement or high-value feature selection—finding the exact optimal solution is essential. This paper introduces BB-ICG+, a branch-and-bound framework designed to find exact solutions significantly faster than previous state-of-the-art methods.

Methodology: The BB-ICG+ Framework

The BB-ICG+ algorithm (Branch-and-Bound with Improved Constraint Generation) improves upon traditional exact solvers by integrating three core components:

1. Improved Constraint Generation (ICG)

Exact solvers typically model submodular maximization as a Binary Integer Programming (BIP) problem. Because the number of constraints in this formulation is exponential, standard methods use an iterative approach, adding one constraint at a time. The authors identified this as a bottleneck and developed SUB-ICG, a heuristic that identifies and adds a set of promising constraints simultaneously. This drastically reduces the number of BIP subproblems that must be solved.

2. Hybrid Bounding and Pruning

Branch-and-bound algorithms rely on "pruning" to discard branches of the search tree that cannot contain the optimal solution. BB-ICG+ employs a two-tier bounding strategy:

  • Modular Upper Bound ($h_{dom}$): A computationally inexpensive bound used to quickly prune easy nodes.
  • BIP-based Bound: A tighter but more expensive bound derived from the BIP formulation, solved only when the modular bound is insufficient.

3. Local Search (LS)

At each node in the search tree, the algorithm performs a local search to improve the current best feasible solution (the lower bound). By identifying high-quality solutions early in the search process, the algorithm can prune larger sections of the search tree more effectively.

Experimental Evaluation

The researchers evaluated BB-ICG+ against benchmark problems, specifically Facility Location (LOC)—maximizing benefit for clients—and Weighted Coverage (COV)—maximizing sensor coverage. Testing involved instances with set sizes ($n$) up to 55 and cardinality constraints ($k$) of 5 and 8. While these dimensions appear small, the combinatorial complexity makes them highly challenging for exact optimization.

Key Results

  • Reliability: BB-ICG+ was the only algorithm to solve 100% of the test instances within the one-hour time limit.
  • Efficiency: On average, the standard A search (A-DOM) was over 48 times slower than BB-ICG+.
  • Pruning Power: In a Facility Location test ($n=55, k=8$), BB-ICG+ reached the optimum in approximately 3 minutes by processing only 180 nodes. In contrast, the A* search failed to complete within the hour, typically exploring millions of nodes without reaching a conclusion.

Conclusion and Future Work

BB-ICG+ demonstrates that exact submodular maximization is feasible for moderately sized problems by combining efficient constraint generation with aggressive pruning and local search. However, the current implementation is limited to monotone (non-decreasing) submodular functions and simple cardinality constraints.

Future research directions include extending the framework to handle non-monotone functions and more complex constraints, such as knapsack or matroid constraints. Additionally, further refinements are required to scale the algorithm to "Big Data" contexts where $n$ exceeds 100 elements.

Summary updated

Abstract

The submodular function maximization is an attractive optimization model that appears in many real applications. Although a variety of greedy algorithms quickly find good feasible solutions for many instances while guaranteeing (1-1/e)-approximation ratio, we still encounter many real applications that ask optimal or better feasible solutions within reasonable computation time. In this paper, we present an efficient branch-and-bound algorithm for the non-decreasing submodular function maximization problem based on its binary integer programming (BIP) formulation with a huge number of constraints. Nemhauser and Wolsey developed an exact algorithm called the constraint generation algorithm that starts from a reduced BIP problem with a small subset of constraints taken from the constraints and repeats solving a reduced BIP problem while adding a new constraint at each iteration. However, their algorithm is still computationally expensive due to many reduced BIP problems to be solved. To overcome this, we propose an improved constraint generation algorithm to add a promising set of constraints at each iteration. We incorporate it into a branch-and-bound algorithm to attain good upper bounds while solving a smaller number of reduced BIP problems. According to computational results for well-known benchmark instances, our algorithm achieved better performance than the state-of-the-art exact algorithms.
BibTeX
@misc{uematsu2018efficient,
  author = {Naoya Uematsu and Shunji Umetani and Yoshinobu Kawahara},
  title = {{An efficient branch-and-bound algorithm for submodular function maximization}},
  year = {2018},
  eprint = {1811.04177},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.04177},
}
Figure