Advanced search
Start date

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

Grant number: 12/06027-5
Support Opportunities: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 - 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


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)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list using this form.