The min-Knapsack problem with compactness constraints and applications in statistics

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Santini, Alberto
• dc.contributor.author Malaguti, Enrico
• dc.date.accessioned 2024-02-23T07:44:18Z
• dc.date.available 2024-02-23T07:44:18Z
• dc.date.issued 2023
• dc.description.abstract In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper, we introduce an extension of the min-Knapsack problem with additional “compactness constraints” (mKPC), stating that selected items cannot lie too far apart. This extension has applications in statistics, including in algorithms for change-point detection in time series. We propose three solution methods for the mKPC. The first two methods use the same Mixed-Integer Programming (MIP) formulation but with two different approaches: passing the complete model with a quadratic number of constraints to a black-box MIP solver or dynamically separating the constraints using a branch-and-cut algorithm. Numerical experiments highlight the advantages of this dynamic separation. The third approach is a dynamic programming labelling algorithm. Finally, we focus on the particular case of the unit-cost mKPC (1c-mKPC), which has a specific interpretation in the context of the statistical applications mentioned above. We prove that the 1c-mKPC is solvable in polynomial time with a different ad-hoc dynamic programming algorithm. Experimental results show that this algorithm vastly outperforms both generic approaches for the mKPC and a simple greedy heuristic from the literature.
• dc.format.mimetype application/pdf
• dc.identifier.citation Santini A, Malaguti E. The min-Knapsack problem with compactness constraints and applications in statistics. Eur J Oper Res. 2023;312:385-97. DOI: 10.1016/j.ejor.2023.07.020
• dc.identifier.doi http://dx.doi.org/10.1016/j.ejor.2023.07.020
• dc.identifier.issn 0377-2217
• dc.identifier.uri http://hdl.handle.net/10230/59230
• dc.language.iso eng
• dc.publisher Elsevier
• dc.relation.ispartof European Journal of Operational Research. 2023;312:385-97.
• dc.rights © 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.rights.uri https://creativecommons.org/licenses/by/4.0/
• dc.subject.keyword Cutting
• dc.subject.keyword Knapsack problems
• dc.subject.keyword Applications in statistics
• dc.subject.keyword Dynamic programming
• dc.title The min-Knapsack problem with compactness constraints and applications in statistics
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/publishedVersion