QKBP: A Fast and Effective Breakpoints Heuristic Algorithm for the Quadratic Knapsack Problem

This software produces solutions to the well-known Quadratic Knapsack Problem (QKP). The QKP is to select a subset of elements that maximizes the sum of pairwise and singleton utilities such that the sum of weights of the elements in the selected subset does not exceed a given budget. A detailed description of the software can be found in our paper https://doi.org/10.1016/j.ejor.2024.12.019.

Installation

1. Clone the repository.

2. Compile the C code of the simple parametric cut procedure QKPsimparamHPF.c with a GNU C compiler.

   For Linux/Mac users:

   1. Open a terminal and navigate to the folder that contains the file QKPsimparamHPF.c.
   2. Compile the C code with the command:

      gcc QKPsimparamHPF.c -o QKPsimparamHPF.exe

   For Windows users:

   1. Install Cygwin.
   2. Open the Cygwin shell and navigate to the folder that contains the file QKPsimparamHPF.c.
   3. Compile the C code with the command:

      gcc QKPsimparamHPF.c -o QKPsimparamHPF.exe

3. Create a virtual environment and install the packages in requirements.txt

   pip install -r requirements.txt

4. All set, you can now run the algorithm in the run_illustrative_example.py or run_instance.py file.

Usage

Import the run_bp_algorithm function from the breakpoints_algorithm module and the load_instance function from the util module. Then, load a problem instance from a file and run the breakpoints algorithm.

from breakpoints_algorithm import run_bp_algorithm
from util import load_instance

# Load a problem instance from a file
elements, utilities, weights, budgets = load_instance('data/synthetic_tf_2000.txt')

# Run the breakpoints algorithm
results = run_bp_algorithm(elements, utilities, weights, budgets, n_lambda_values=1600)

The run_bp_algorithm function takes the following parameters:

• elements: A list of elements.
• utilities: A dictionary where the keys are pairs of elements and the values are the corresponding utilities. A singleton utility is represented as a pair of the same element.
• weights: A list containing the weights for each element.
• budgets: A list of knapsack capacities. A separate solution will be computed for each capacity.
• n_lambda_values: The number of lambda values to consider in the breakpoints algorithm.

The file that contains the problem instance should have the following format:

first line: number of elements (n), number of utilities (m), data type of utilities (int or float)
lines 2 to m+1: (i, j, utility) for each utility value where i and j are the ids of the elements. The ids should be 0,...,n-1.
line m+2: weights of the elements separated by a space
line m+3: budgets (knapsack capacities) separated by a space

Reference

Please cite the following paper if you use this code.

Hochbaum, D. S., Baumann, P., Goldschmidt O., Zhang Y. (2024): A fast and effective breakpoints heuristic algorithm for the quadratic knapsack problem. European Journal of Operational Research, In Press, URL: https://doi.org/10.1016/j.ejor.2024.12.019

Bibtex:

@article{hochbaum2024fast,
  title={A fast and effective breakpoints heuristic algorithm for the quadratic knapsack problem},
  author={Hochbaum, DS and Baumann, P and Goldschmidt, O and Zhang, Y},
  journal={European Journal of Operational Research},
  year={2024},
  note={In Press},
  doi={10.1016/j.ejor.2024.12.019},
  publisher={Elsevier}
}

• Link to paper
• Link to the detailed results of the computational study conducted in the paper
• Link to all benchmark instances used in the computational study conducted in the paper

License

This project is licensed under the MIT License - see the LICENSE file for details