Estratégias de exploração de vizinhança com GPU para problemas de otimização

Abstract

Optimization problems have big importance in the industry field, from production management to production outflow and product transportation. Many problems of interest are classified as NP-Hard, so there is no known algorithm to find the exact solution in a polinomial time. Therefore heuristic strategies with the ability to escape from poor quality local optima (meta-heuristics) are generally employed. In general, the local search is the most costly, in computational time, phase of a meta-heuristic, becoming mandatory a good use of the available resources. The parallel processing of neighborhood strategies is implemented at the fine grain level through GPU processing and coarse grain through multi-core processing and network processing, the combination of the two level parallelization in a heterogeneous environment for von Neumann architectures and dataflow