Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.17543 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916707190177792 |
|---|---|
| author | Villuendas, Hubert Besançon, Mathieu Malick, Jérôme |
| author_facet | Villuendas, Hubert Besançon, Mathieu Malick, Jérôme |
| contents | The min-knapsack problem with compactness constraints extends the classical knapsack problem, in the case of ordered items, by introducing a restriction ensuring that they cannot be too far apart. This problem has applications in statistics, particularly in the detection of change-points in time series. In this paper, we propose a semidefinite programming approach for this problem, incorporating compactness in constraints or in objective. We study and compare the different relaxations, and argue that our method provides high-quality heuristics and tight bounds. In particular, the single hyperparameter of our penalized semidefinite models naturally balances the trade-off between compactness and accuracy of the computed solutions. Numerical experiments illustrate, on the hardest instances, the effectiveness and versatility of our approach compared to the existing mixed-integer programming formulation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17543 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Knapsack with compactness: a semidefinite approach Villuendas, Hubert Besançon, Mathieu Malick, Jérôme Optimization and Control The min-knapsack problem with compactness constraints extends the classical knapsack problem, in the case of ordered items, by introducing a restriction ensuring that they cannot be too far apart. This problem has applications in statistics, particularly in the detection of change-points in time series. In this paper, we propose a semidefinite programming approach for this problem, incorporating compactness in constraints or in objective. We study and compare the different relaxations, and argue that our method provides high-quality heuristics and tight bounds. In particular, the single hyperparameter of our penalized semidefinite models naturally balances the trade-off between compactness and accuracy of the computed solutions. Numerical experiments illustrate, on the hardest instances, the effectiveness and versatility of our approach compared to the existing mixed-integer programming formulation. |
| title | Knapsack with compactness: a semidefinite approach |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2504.17543 |