Treffer: A cut-and-branch algorithm for the quadratic knapsack problem
Title:
A cut-and-branch algorithm for the quadratic knapsack problem
Publisher Information:
2020-03-04
Document Type:
E-Ressource
Electronic Resource
Index Terms:
URL:
Availability:
Open access content. Open access content
creative_commons_attribution_noncommercial_noderivatives_4_0_international_license
creative_commons_attribution_noncommercial_noderivatives_4_0_international_license
Note:
Other Numbers:
HR0 oai:eprints.lancs.ac.uk:141820
https://eprints.lancs.ac.uk/id/eprint/141820/1/qkp2.pdf
Djeumou Fomeni, Franklin and Kaparis, Konstantinos and Letchford, Adam (2020) A cut-and-branch algorithm for the quadratic knapsack problem. Discrete Optimization. ISSN 1572-5286
1201477960
https://eprints.lancs.ac.uk/id/eprint/141820/1/qkp2.pdf
Djeumou Fomeni, Franklin and Kaparis, Konstantinos and Letchford, Adam (2020) A cut-and-branch algorithm for the quadratic knapsack problem. Discrete Optimization. ISSN 1572-5286
1201477960
Contributing Source:
LANCASTER UNIV LIBR
From OAIster®, provided by the OCLC Cooperative.
From OAIster®, provided by the OCLC Cooperative.
Accession Number:
edsoai.on1201477960
Database:
OAIster
Weitere Informationen
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.