Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
481057 | European Journal of Operational Research | 2010 | 10 Pages |
Abstract
Given an unconstrained quadratic optimization problem in the following form:(QP)min{xtQx|x∈{-1,1}n},with Q∈Rn×nQ∈Rn×n, we present different methods for computing bounds on its optimal objective value. Some of the lower bounds introduced are shown to generally improve over the one given by a classical semidefinite relaxation. We report on theoretical results on these new bounds and provide preliminary computational experiments on small instances of the maximum cut problem illustrating their performance.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Walid Ben-Ameur, José Neto,