An exact solver for submodular knapsack problems
提出了一种针对子模背包问题的精确分支定界算法，并开发了多种加速技术，在人工和真实数据集上验证了其高效性，适用于需要精确解的优化场景。
We study the problem of maximizing a monotone increasing submodular function over a set of weighted elements subject to a knapsack constraint. Although this problem is NP-hard, many applications require exact solutions, as approximate solutions are often insufficient in practice. To address this need, we propose an exact branch-and-bound algorithm tailored for the submodular knapsack problem and introduce several acceleration techniques to enhance its efficiency. We evaluate these techniques on artificial instances of three benchmark problems as well as on instances derived from real-world data. We compare the proposed solver with two solvers by Sakaue and Ishihata(2018) as well as with a branch-and-cut algorithm implemented using Gurobi that solves a binary linear reformulation of the submodular knapsack problem, demonstrating that our methods are highly successful. • An exact branch-and-bound algorithm for the submodular knapsack problem. • We developed several acceleration techniques for this branch-and-bound algorithm. • Computational experiments show that the acceleration techniques are highly effective.