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 productionmanagement to production outflow and product transportation. Many problems of inte-rest are classified as NP-Hard, so there is no known algorithm to find the exact solutionin a polinomial time. Therefore heuristic strategies with the ability to escape from poorquality local optima (meta-heuristics) are generally employed. In general, the local searchis the most costly, in computational time, phase of a meta-heuristic, becoming mandatorya good use of the available resources. The parallel processing of neighborhood strategiesis implemented at the fine grain level through GPU processing and coarse grain throughmulti-core processing and network processing, the combination of the two level paralleli-zation in a heterogeneous environment for von Neumann architectures and dataflow.