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

• Grant number: 12/06027-5
• Support Opportunities: Scholarships in Brazil - Master
• Start date: June 01, 2012
• End date: May 31, 2013
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Cláudio Nogueira de Meneses
• Grantee: Eduardo Batista Gomes Moreira
• Host 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)