Advanced search
Start date
Betweenand

Methods for solving quadratic binary optimization problems

Grant number: 18/03819-4
Support type:Scholarships in Brazil - Doctorate
Effective date (Start): June 01, 2018
Effective date (End): May 31, 2021
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Cláudio Nogueira de Meneses
Grantee:Eduardo Alves de Jesus Anacleto
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:16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings, AP.TEM

Abstract

In this project, we investigate the Unconstrained Binary Quadratic Programming (UBQP) problem and the Boolean Quadratic Programming problem with Generalized Upper Bound constraints BQP-GUB, which belong to the computational complexity class NP-hard. Due to practical demands, researchers have shown interest in developing methods to solve these problems. To make relevant contributions, we intend to: (a) develop an exact method for the UBQP problem; (b) design a polynomial time algorithm for solving instance classes of the UBQP problem; (c) propose a parallel version of the methods indicated in items (a) and (b); (d) develop a formula to generate bounds on the optimal solution values for solving instances of the UBQP problem; (e) develop formulas for evaluating flip-moves that simultaneously change the value of components of a solution vector for the BQP-GUB problem; (f) reformulate combinatorial optimization problems to the form of UBQP and BQP-GUB problems. Despite the objectives are ambitious, in the last six months, we proved original results with respect to the items (a), (b), (d) and (e). We also have conducted computational experiments for the methods related to the items (a) and (b). It is worth to say that these preliminary results, theoretical and computational, are encouraging.

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
ANACLETO, EDUARDO A. J.; MENESES, CLAUDIO N.; RAVELO, SANTIAGO V. Closed-form formulas for evaluating r-flip moves to the unconstrained binary quadratic programming problem. Computers & Operations Research, v. 113, JAN 2020. Web of Science Citations: 0.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.