A Development and Deployment Framework for Distributed Branch & Bound

Abstract

Branch and bound is described briefly. Some discussion is given about extant work on branch and bound, parallel implementations, distributed implementations, fault-tolerant issues, and frameworks for developing branch and bound software. The distributed deployment architecture is described: essentially, a network of task servers, each of which services a set of compute servers. Some architectural performance enhancements are described which reduce or hide the latency of communicating computational tasks between task servers and compute servers. Then, the model of computation and the branch and bound API are presented. Experiments are described where a medium-complexity Travelling Salesman Problem branch and bound code is run on a 200-city TSPLIB problem instance. For a cluster of up to 120 processors, speedups were never less than 94% of ideal. The efficiency of their compute server fault tolerant mechanism was measured. Starting with 32 processors, various numbers of the processors were killed (from 4 to 28). The resulting slowdown (i.e., the overhead incurred by recovery) was never more than 9.4%. They also present some experimental data indicating that, for branch and bound, the task server that is needed to service a set of compute servers can run on the same machine as one of the compute servers with essentially no loss of efficiency.

BibTex

@inbook{cappello:aam

	author =	{Peter Cappello and Christopher James Coakley},
	title =		{{A Development and Deployment Framework for Distributed Branch \& Bound}},
	booktitle =	{Approximation Algorithms and Metaheuristics},
	publisher =	{CRC Press},
	year = {2007},
	chapter = {41},
	pages = {41-1 - 41-11},
	address = {},
	note = {T. Gonzales(ed.). },
}

Full version - pdf file