knapsackProblemInstances: A C++ repository from cainafigueiredo

This repository contains the data described in the paper: "A new class of hard problem instances for the 0-1 knapsack problem". This paper has been published in European Journal of Operational Research. Please cite this paper as:

Jooken, J., Leyman, P., & De Causmaecker, P. (2022). A new class of hard problem instances for the 0–1 knapsack
problem. European Journal of Operational Research, 301, 841–854.

The corresponding BibTeX entry is:

@article{Jooken:2022,
  title={A new class of hard problem instances for the 0--1 knapsack problem},
  author={Jooken, Jorik and Leyman, Pieter and De Causmaecker, Patrick},
  journal={European Journal of Operational Research},
  volume={301},
  number={3},
  pages={841--854},
  year={2022},
  publisher={Elsevier}
}

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

This repository contains a problem instance generator for the 0-1 knapsack problem
and a dataset of 3240 problem instances generated using the given generator.

* GENERATOR *

The generator source code is given in generator.cpp and its executable is called generatorExecutable. We assume a Linux working environment.
To generate a fresh copy of the executable, the source code needs to be recompiled ("g++ -g -std=c++11 -O2 generator.cpp -o generatorExecutable").
The generator expects six parameters as input that will be read from the standard input stream. The order in which the parameters
will be read from the standard input stream is as follows (from first to last): n, c, g, f, epsilon and s.

The repository also contains a file called "testInputForGenerator.txt", in which five parameters are given.
To generate a problem instance using these parameters, type in a terminal "./generatorExecutable < testInputForGenerator.txt > toyProblemInstance.txt".

* PROBLEM INSTANCES *

The problem instances are located in the folder "problemInstances".
Every problem instance is located in a separate subfolder for which the name describes
the features of that problem instance (the parameters used by the generator to generate the problem instance).

Every subfolder contains 3 files:
1) test.in - the problem instance. The first line of this file represents the number of items, n. Each of the n following lines describe an item and contains 3 integers: the id of the item, the profit of the item and the weight of the item. The last line contains an integer describing the knapsack capacity, c.

For example, if the file contains the following:
"
3
1 3 8
2 2 8
3 9 1
10
"

This describes a problem instance in which there are n=3 items and the knapsack has a capacity of c=10. The item with id 1 has a profit of 3 and a weight of 8.
The item with id 2 has a profit of 2 and a weight of 8. The item with id 3 has a profit of 9 and a weight of 1.

2) outp.out - the output generated by combo when solving the problem instance in this folder. In case combo was able to solve
 the problem instance without running out of time or memory, this file will contain on the first line the sum of the profits of the selected items
and on the subsequent lines the description of the items that should be included into the knapsack. Every item will be described in a separate line
 by its profit and weight. For example, if the file contains the following:

"
12
3 8
9 1
"

This represents that the optimal solution has a total profit of 12, which can be obtained by selecting an item with profit 3 and weight 8 and another item
with profit 9 and weight 1.

In case combo was not able to solve the problem instance without running out of time or memory, this file will contain the error message produced by combo (if any).

3) time.out - in case combo was able to solve the problem instance without running out of time or memory, this file will contain the time that was used
by combo to do so (in seconds). Otherwise, this file will contain "-1".


* COMBO EXECUTABLE *

This repository also contains the file "comboExecutable" - the executable of the combo algorithm to solve 0-1 knapsack problem instances (source code available at: http://hjemmesider.diku.dk/~pisinger/codes.html)

* OPTIMA *

The optimal objective function values for the 3240 problem instances are summarized in the file "optima.csv". In case combo was able to solve the problem instance without running out of time or memory, the optimal objective function value will be reported. Otherwise, we report a sentinel value "-1".

* PRELIMINARY EXPERIMENT *

The names of the 100 problem instances used in the preliminary experiment can be found in "preliminaryExperiment100Names.txt"
cainafigueiredo/knapsackProblemInstances
