Advanced search
Start date
Betweenand

GPU-Based parallel algorithms for solving unconstrained binary quadratic programming problems

Grant number: 12/06027-5
Support type:Scholarships in Brazil - Master
Effective date (Start): June 01, 2012
Effective date (End): May 31, 2013
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Cláudio Nogueira de Meneses
Grantee:Eduardo Batista Gomes Moreira
Home Institution: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brazil
Associated research grant:10/10133-0 - Cutting, packing, lot-sizing and scheduling problems and their integration in industrial and logistics settings, AP.TEM

Abstract

In this project we intend to design GPU-based algorithms to solve unconstrained binary quadratic programming problems (UQP). These problems consist of minimize or maximize a quadratic function over binary numbers. Many combinatorial optimization problems can be put in the UQP form, for example k-coloring graph, maximum clique, maximum independent set, etc. In particular, we intend to solve cutting and packing problems. A relevant problem in this field is the manufacturer's pallet loading problem (MPL) which consists of packing identical items (for example boxes) into larger objects (pallets). The MPL can be viewed as a maximum independent set and this can be transformed to the UQP form. (AU)