The parallel solution of some discrete optimization problems

Abstract

Aims at the parallel solution of two discrete optimisation problems, namely the 0-1 rucksack problem (0-1KP) and the symmetrical commercial traveller's problem (SHP). The solution of the 0-1KP requires that the objects be sorted, and for this reason the parallel solution of the sorting problem was also addressed. Parallel algorithms are proposed for each of the three problems, and the experimental results obtained on a transputer network are reported. The parallel algorithms are new algorithms, mostly combinations of sequential algorithms or based on these algorithms, e.g. the branch-and-cut algorithm. The results were obtained by using these algorithms on an existing parallel computer, not simulation of a parallel algorithm on a sequential computer, and indicate a suitability for large-scale problems.