Scholarship 18/03819-4 - Programação dinâmica, Otimização combinatória - BV FAPESP
Advanced search
Start date
Betweenand

Methods for Solving Quadratic Binary Optimization Problems

Grant number: 18/03819-4
Support Opportunities:Scholarships in Brazil - Doctorate
Start date until: June 01, 2018
End date until: May 31, 2022
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Computational Mathematics
Principal Investigator:Cláudio Nogueira de Meneses
Grantee:Eduardo Alves de Jesus Anacleto
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: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.

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

Scientific publications (4)
(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, . (18/03819-4)
RAVELO, SANTIAGO, V; MENESES, CLAUDIO N.; ANACLETO, EDUARDO A. J.; IEEE. NP-hardness and evolutionary algorithm over new formulation for a Target Set Selection problem. 2020 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), v. N/A, p. 8-pg., . (18/03819-4)
LIANG, RICARDO N.; ANACLETO, EDUARDO A. J.; MENESES, CLAUDIO N.. Data structures for speeding up Tabu Search when solving sparse quadratic unconstrained binary optimization problems. Journal of Heuristics, v. 28, n. 4, p. 47-pg., . (18/03819-4)
LIANG, RICARDO N.; ANACLETO, EDUARDO A. J.; MENESES, CLAUDIO N.. Fast 1-flip neighborhood evaluations for large-scale pseudo-Boolean optimization using posiform representation. Computers & Operations Research, v. 159, p. 16-pg., . (18/03819-4)

Please report errors in scientific publications list using this form.