Advanced search
Start date

Reformulations of binary optimization problems: algorithms and complexity

Grant number: 14/23269-8
Support Opportunities:Scholarships in Brazil - Post-Doctoral
Effective date (Start): March 01, 2015
Effective date (End): February 28, 2017
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Computational Mathematics
Principal Investigator:Carlos Eduardo Ferreira
Grantee:Aritanan Borges Garcia Gruber
Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Associated research grant:13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science, AP.TEM


Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case.Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision and machine learning, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables.The focus of this project is to further study and develop these quadratization approaches (from both theoretical and practical standpoints), and to investigate possible relations that they may have with other strategies that appear in the literature, like hierarchies of relaxations / extended formulations and sum-of-squares of polynomials. (AU)

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

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)
ANTHONY, MARTIN; BOROS, ENDRE; CRAMA, YVES; GRUBER, ARITANAN. Quadratization of symmetric pseudo-Boolean functions. DISCRETE APPLIED MATHEMATICS, v. 203, p. 1-12, . (14/23269-8)
ANTHONY, MARTIN; BOROS, ENDRE; CRAMA, YVES; GRUBER, ARITANAN. Quadratic reformulations of nonlinear binary optimization problems. MATHEMATICAL PROGRAMMING, v. 162, n. 1-2, p. 115-144, . (14/23269-8)

Please report errors in scientific publications list by writing to: