Knapsack with compactness: a semidefinite approach
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- On Integrality in Semidefinite Programming for Discrete OptimizationSIAM Journal on Optimization, 2024
- The min-Knapsack problem with compactness constraints and applications in statisticsEuropean Journal of Operational Research, 2023
- JuMP 1.0: recent improvements to a modeling language for mathematical optimizationMathematical Programming Computation, 2023
- Knapsack polytopes: a surveyAnnals of Operations Research, 2019
- Parallelizing the dual revised simplex methodMathematical Programming Computation, 2017
- A recipe for semidefinite relaxation for (0,1)-quadratic programmingJournal of Global Optimization, 1995