min-knapsack-with-compactness

Algorithms for the min-Knapsack problem with compactness constraints.

https://github.com/alberto-santini/min-knapsack-with-compactness

Science Score: 67.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • CITATION.cff file
    Found CITATION.cff file
  • codemeta.json file
    Found codemeta.json file
  • .zenodo.json file
    Found .zenodo.json file
  • DOI references
    Found 5 DOI reference(s) in README
  • Academic publication links
    Links to: zenodo.org
  • Academic email domains
  • Institutional organization owner
  • JOSS paper metadata
  • Scientific vocabulary similarity
    Low similarity (10.0%) to scientific vocabulary

Keywords

change-point-detection knapsack-problem time-series variable-selection
Last synced: 6 months ago · JSON representation ·

Repository

Algorithms for the min-Knapsack problem with compactness constraints.

Basic Info
  • Host: GitHub
  • Owner: alberto-santini
  • License: bsd-2-clause
  • Language: C++
  • Default Branch: master
  • Homepage:
  • Size: 1.81 MB
Statistics
  • Stars: 2
  • Watchers: 1
  • Forks: 0
  • Open Issues: 0
  • Releases: 1
Topics
change-point-detection knapsack-problem time-series variable-selection
Created over 3 years ago · Last pushed over 2 years ago
Metadata Files
Readme License Citation

README.md

Sample solution

Min-Knapsack Problem with Compactness Constraints

DOI

This is a collection of algorithms to solve:

  • The min-Knapsack Problem with Compactness Constraints (mKPC), a generalisation of the classical min-Knapsack problem. The mKPC arises as a sub-problem in some algorithms for change-point detection in time series analysis (such as the PRISCA algorithm) and for variable selection in genetic fine-mapping (such as the SuSiE algorithm).
  • The unit-cost mKPC, a polynomially-solvable particular case of the mKPC.

This software was developed as part of the following manuscript:

bib @article{Santini_Malaguti_2023 title={The min-Knapsack Problem with Compactness Constraints and Applications in Statistics}, author={Santini, Alberto and Malaguti, Enrico}, journal={European Journal of Operational Research}, doi={10.1016/j.ejor.2023.07.020}, year=2024, volume=312, issue=1, pages={385--397} }

You can cite this repository itself as follows:

bib @misc{Santini_2022, title={Algorithms for the min-Knapsack problem with compactness constraints}, author={Santini, Alberto}, date={2022-12-29}, year=2022, doi={10.5281/zenodo.7492799}, url={https://github.com/alberto-santini/min-knapsack-with-compactness}, howpublished={Github repository} }

Data

  • Data in data/cappello-raw-data is raw csv data from Cappello and Madrid Padilla.
  • Data in data/cappello-instances is JSON data created starting from the above csv data, using data/cappello_transform_raw_data.py.
  • Data in data/synthetic-instances is data generated by us using data/generator.py.

Licence

Released under the 2-clause BSD licence. Refer to the file LICENSE in the repository's root directory.

Included software:

Owner

  • Name: Alberto Santini
  • Login: alberto-santini
  • Kind: user
  • Location: Barcelona, Spain

Citation (CITATION.cff)

cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: "Santini"
  given-names: "Alberto"
  orcid: "https://orcid.org/0000-0002-0440-0357"
title: "Algorithms for the min-Knapsack problem with compactness constraints"
version: 0.1
doi: 10.5281/zenodo.7492799
date-released: 2020-12-29
url: "https://github.com/alberto-santini/min-knapsack-with-compactness"
preferred-citation:
  type: article
  authors:
  - family-names: "Santini"
    given-names: "Alberto"
    orcid: "https://orcid.org/0000-0002-0440-0357"
  - family-names: "Malaguti"
    given-names: "Enrico"
  journal: "European Journal of Operational Research"
  title: "The min-Knapsack Problem with Compactness Constraints and Applications to Statistics"
  year: 2024
  volume: 312
  issue: 1
  start: 385
  end: 397
  doi: "10.1016/j.ejor.2023.07.020"

GitHub Events

Total
Last Year