Data storage with the Multiple Knapsack Problem (MKP)

This project was made as a school project in order to find how to solve a Multiple Knapsack Proble

Solution

MKP

here:

• The collections (Knapsacks) are the SystemNodes;
• The items to place in are the Data;
• The weight of each item is size of the Data;
• The max weight of the collection is the capacity of the SystemNode;
• The value of each item is the inverse of the quadratic mean of weighted distances from all users that are interested in the data;

My way to solve it

As in the MKP, the objective is to pick some of the items, with maximal total profit p, while obeying that the maximum total weight w of the chosen items that must not exceed the max weight W of each collection. As the project involve an MKP, we place data on the node where it have the best profit and the solve single nodes as a 0-1 knapsack problem. Then we take items that not fit in the collection and loop the algorithm removing already filled nodes.

Getting Started

These instructions will get you a copy of the project up and running on your local machine for development and testing purposes. See deployment for notes on how to deploy the project on a live system.

Prerequisites

To be able to run the project, you need to have java 8 or upper installed and as well as maven

Running the project

You first need to clone the project

git clone git@github.com:nowtryz/data-storage.git
cd data-storage

From command line

To run the project, follow the steps bellow:

• package the app with maven

  mvn clean package

• run the archive

  java -jar taget/data-storage-1.0-SNAPSHOT.jar

From IntelliJ

Open the .iml module

Built With

• Maven - Dependency Management
• JGraphT - Used to manipulate graphs

Versioning

We use SemVer for versioning. For the versions available, see the tags on this repository.

License

This project is licensed under the MIT License