Knapsack with compactness: a semidefinite approach

Poster session. Poster

The min-knapsack with compactness constraint problem (min-KCP) is a variant of the classical knapsack problem, introduced in The min-Knapsack problem with compactness constraints and applications in statistics, originally to solve the problem of detecting regime changes in time series. Given items \(i\in \left\lbrace 1,\dots,n\right\rbrace\) with cost \(c_i\) and weight \(w_i\), the goal is to select objects \(S\subseteq\left\lbrace 1,\dots,n\right\rbrace\) minimizing the cost of the selection, while ensuring that the total weight exceeds a given constant \(q\), in such a way that the selection is compact: for a given \(\Delta\in\mathbb{N}\), the distance separating two consecutive selected objects \(i,j\in S\) must not exceed \(\Delta\).

In this work, we propose a semidefinite reformulation of this problem, and explain how to strengthen the baseline semidefinite relaxation in order to get better bounds, and show how the semidefinite model compares with the well-known classical cuts for the knapsack problem, such as cover inequalities.

A second part of the work focuses on the efficiency of penalized versions of the semidefinite relaxation and how this approach can effectively address the original statistical problem.