ISSN:
1573-2886
Keywords:
semidefinite programming
;
quadratic knapsack problem
;
cutting planes
;
0/1 polytopes
;
relaxations
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract In order to gain insight into the quality of semidefinite relaxations of constrained quadratic 0/1 programming problems we study the quadratic knapsack problem. We investigate several basic semidefinite relaxations of this problem and compare their strength in theory and in practice. Various possibilities to improve these basic relaxations by cutting planes are discussed. The cutting planes either arise from quadratic representations of linear inequalities or from linear inequalities in the quadratic model. In particular, a large family of combinatorial cuts is introduced for the linear formulation of the knapsack problem in quadratic space. Computational results on a small class of practical problems illustrate the quality of these relaxations and cutting planes.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1009898604624
Permalink
