In this paper we describe a fundamentally new approach to the exact solution of combinatorial optimisation problems on parallel computers, based on the synergistic use of exact and stochastic/heuristic techniques. We show the effectiveness of the proposed method with reference to the 0/1 knapsack problem; by using a cluster of two IBM RISC 6000 connected via TCP/IP, we obtained an average speed-up of 3.8 on 10 instances of a problem with 5000 items.
展开▼
