An Exact Solver for Submodular Knapsack Problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909855683444736 |
|---|---|
| author | Münch, Sabine Raach, Stephen |
| author_facet | Münch, Sabine Raach, Stephen |
| contents | 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), which currently achieve the strongest performance reported in the literature, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_16149 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Exact Solver for Submodular Knapsack Problems Münch, Sabine Raach, Stephen Data Structures and Algorithms Discrete Mathematics 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), which currently achieve the strongest performance reported in the literature, 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. |
| title | An Exact Solver for Submodular Knapsack Problems |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2507.16149 |