Optimization Online


A Cut-and-Branch Algorithm for the Quadratic Knapsack Problem

Franklin Djeumou Fomeni(F.DjeumouFomeni***at***lancaster.ac.uk)
Konstantinos Kaparis(K.Kaparis***at***lancaster.ac.uk)
Adam N Letchford(A.N.Letchford***at***lancaster.ac.uk)

Abstract: The Quadratic Knapsack Problem (QKP) is a much-studied 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 much more sophisticated than existing ones in the literature, incorporating several classes of cutting planes, a primal heuristic, and several rules for eliminating both variables and constraints. Computational results show that the algorithm is capable of solving instances of the QKP that cannot be solved by other methods.

Keywords: knapsack problems; cutting planes; integer programming

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Working paper, Department of Management Science, Lancaster University, United Kingdom.

Download: [PDF]

Entry Submitted: 05/31/2014
Entry Accepted: 06/01/2014
Entry Last Modified: 05/31/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society