Home > Research > Publications & Outputs > A cut-and-branch algorithm for the quadratic kn...

Research

Associated organisational units

Electronic data

  • qkp2

    Rights statement: This is the author’s version of a work that was accepted for publication in Discrete Optimization. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Optimization, 44, 2, 2022 DOI: 10.1016/j.disopt.2020.100579

    Accepted author manuscript, 445 KB, PDF document

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

A cut-and-branch algorithm for the quadratic knapsack problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

A cut-and-branch algorithm for the quadratic knapsack problem. / Djeumou Fomeni, Franklin; Kaparis, Konstantinos; Letchford, Adam.
In: Discrete Optimization, Vol. 44, No. 2, 100579, 31.05.2022.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Djeumou Fomeni, F, Kaparis, K & Letchford, A 2022, 'A cut-and-branch algorithm for the quadratic knapsack problem', Discrete Optimization, vol. 44, no. 2, 100579. https://doi.org/10.1016/j.disopt.2020.100579

APA

Djeumou Fomeni, F., Kaparis, K., & Letchford, A. (2022). A cut-and-branch algorithm for the quadratic knapsack problem. Discrete Optimization, 44(2), Article 100579. https://doi.org/10.1016/j.disopt.2020.100579

Vancouver

Djeumou Fomeni F, Kaparis K, Letchford A. A cut-and-branch algorithm for the quadratic knapsack problem. Discrete Optimization. 2022 May 31;44(2):100579. Epub 2020 Mar 4. doi: 10.1016/j.disopt.2020.100579

Author

Djeumou Fomeni, Franklin ; Kaparis, Konstantinos ; Letchford, Adam. / A cut-and-branch algorithm for the quadratic knapsack problem. In: Discrete Optimization. 2022 ; Vol. 44, No. 2.

Bibtex

@article{8f19db5c5476464cb84ba918e3ea56d3,
title = "A cut-and-branch algorithm for the quadratic knapsack problem",
abstract = "The Quadratic Knapsack Problem (QKP) is a well-known NP-hard combinatorial optimisation problem, with many practical applications. We present a {\textquoteleft}cut-and-branch{\textquoteright} algorithm for the QKP, in which a cutting-plane phase is followed by a branch-and-bound phase. The cutting-plane phase is more sophisticated than the existing ones in the literature, incorporating several classes of cutting planes, two primal heuristics, and several rules for eliminating variables and constraints. Computational results show that the algorithm is competitive.",
keywords = "integer programming, combinatorial optimisation, knapsack problems",
author = "{Djeumou Fomeni}, Franklin and Konstantinos Kaparis and Adam Letchford",
note = "This is the author{\textquoteright}s version of a work that was accepted for publication in Discrete Optimization. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Optimization, 44, 2, 2022 DOI: 10.1016/j.disopt.2020.100579",
year = "2022",
month = may,
day = "31",
doi = "10.1016/j.disopt.2020.100579",
language = "English",
volume = "44",
journal = "Discrete Optimization",
issn = "1572-5286",
publisher = "Elsevier",
number = "2",

}

RIS

TY - JOUR

T1 - A cut-and-branch algorithm for the quadratic knapsack problem

AU - Djeumou Fomeni, Franklin

AU - Kaparis, Konstantinos

AU - Letchford, Adam

N1 - This is the author’s version of a work that was accepted for publication in Discrete Optimization. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Optimization, 44, 2, 2022 DOI: 10.1016/j.disopt.2020.100579

PY - 2022/5/31

Y1 - 2022/5/31

N2 - The Quadratic Knapsack Problem (QKP) is a well-known NP-hard combinatorial optimisation problem, with many practical applications. We present a ‘cut-and-branch’ algorithm for the QKP, in which a cutting-plane phase is followed by a branch-and-bound phase. The cutting-plane phase is more sophisticated than the existing ones in the literature, incorporating several classes of cutting planes, two primal heuristics, and several rules for eliminating variables and constraints. Computational results show that the algorithm is competitive.

AB - The Quadratic Knapsack Problem (QKP) is a well-known NP-hard combinatorial optimisation problem, with many practical applications. We present a ‘cut-and-branch’ algorithm for the QKP, in which a cutting-plane phase is followed by a branch-and-bound phase. The cutting-plane phase is more sophisticated than the existing ones in the literature, incorporating several classes of cutting planes, two primal heuristics, and several rules for eliminating variables and constraints. Computational results show that the algorithm is competitive.

KW - integer programming

KW - combinatorial optimisation

KW - knapsack problems

U2 - 10.1016/j.disopt.2020.100579

DO - 10.1016/j.disopt.2020.100579

M3 - Journal article

VL - 44

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

IS - 2

M1 - 100579

ER -