Linear programming for the 0–1 quadratic knapsack problem

Linear programming for the 0–1 quadratic knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor1999422
Country: Netherlands
Volume: 92
Issue: 2
Start Page Number: 310
End Page Number: 325
Publication Date: Jul 1996
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: branch and bound
Abstract:

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints redundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.

Reviews

Required fields are marked *. Your email address will not be published.