A DVND Local Search Implemented on a Dataflow Architecture for the Minimum Latency Problem

摘要

This paper proposes a dataflow implementation for a local search to solve the Minimum Latency Problem (MLP), a variant of the Traveling Salesman Problem (TSP). Since the problem is NP-Hard, best results in literature report the use of metaheuristic strategies, mainly based on the concept of variable neighborhoods. The dataflow architecture was proposed in the 70's with programs represented as dependency graphs, but von Neumann architecture became the standard computing platform and dataflow has been only considered for theoretical experiments. Many state-of-the-art metaheuristics are harnessing computational power from emerging heterogeneous computing platforms, such as Graphics Processing Units (GPU), requiring to rethink some ideas of classic optimization algorithms in order to properly explore the architecture. We propose a hybrid dataflow architecture (simulated over CPU), where each node contains a GPU implementation that enumerates a neighborhood for the problem. The dataflow architecture uses a distributed network that provides scalability for solving large MLP instances, where each neighborhood exploration is part of a state-of-the-art Distributed Variable Neighborhood Descent (DVND). The whole scenario yield an heterogeneous multi-level parallelization approach that can be used to solve time consuming problems, not being coupled to specific instance or problem.