Min-Knapsack Problem with Compactness Constraints

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:

@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:

@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:

• Licence for cxxopts
• Licence for date
• Licence for nlohmann/json
• Licence for rapidcsv