Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
- 作者：Ferrez ; J.-A. ; Fukuda ; K. ; Liebling ; Th.M.
- 关键词：Combinatorial optimization ; NP-hard ; Zero脙脙脙脙脙脙one ; Quadratic programming ; Zonotope ; Vertex enumeration
- 刊名：European Journal of Operational Research
- 出版年：2005
- 期刊代码：58_03772217
- 类别：et
- 出版时间：October 1, 2005
- 卷：166
- 期：1
- 页码：35-50
- 文件大小：390 K
摘要
We address the weighted max-cut problem, or equivalently the problem of maximizing a quadratic form in n binary variables. If the underlying (symmetric) matrix is positive semidefinite of fixed rank d, then the problem can be reduced to searching the extreme points of a zonotope, thus becoming of polynomial complexity in O(nd芒芒芒1). Reverse search is an efficient and practical means for enumerating the cells of a regular hyperplane arrangement, or equivalently, the extreme points of a zonotope. We present an enhanced version of reverse search of significantly reduced computational complexity that uses ray shooting and is well suited for parallel computation. Furthermore, a neighborhood zonotope edge following descent heuristic can be devised. We report preliminary computational experiments of a parallel implementation of our algorithms.