Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture (Q757239): Difference between revisions

The paper reports on the computational results from running a parallel branch-and-bound algorithm for quadratic 0/1 programs on two hypercube systems: iPSC/1 32-node hypercube at the University of Colorado and iPSC/2 16-node hypercube at Pennsylvania State University. These systems are of distributed memory multiprocessor type with homogeneous multiprocessing application. The report is preceeded by a description of the algorithm which computes lower and upper bounds for the continuous partial derivatives of the free variables used for forcing variables. The parallelization is accomplished by splitting of the enumeration tree into subtrees of a given size which become subproblems for the free nodes of the hypercube.