Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142244 | Operations Research Letters | 2015 | 5 Pages |
Abstract
We propose two exact approaches for non-convex quadratic integer minimization subject to linear constraints where lower bounds are computed by considering ellipsoidal relaxations of the feasible set. In the first approach, we intersect the ellipsoids with the feasible linear subspace. In the second approach we penalize exactly the linear constraints. We investigate the connection between both approaches theoretically. Experimental results show that the penalty approach significantly outperforms CPLEX on problems with small or medium size variable domains.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Christoph Buchheim, Marianna De Santis, Laura Palagi,