Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm

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.

Published in:
European Journal of Operations Research, 166, 1, 35-50
PRO 2004 0804, doi:10.1016/j.ejor.2003.04.011

Note: The status of this file is: Involved Laboratories Only

 Record created 2006-02-13, last modified 2018-11-15

Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
(Not yet reviewed)