Advanced search
Start date
Betweenand

Reformulations of binary optimization problems: algorithms and complexity

Grant number: 14/23269-8
Support type:Scholarships in Brazil - Post-Doctorate
Effective date (Start): March 01, 2015
Effective date (End): February 28, 2017
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Carlos Eduardo Ferreira
Grantee:Aritanan Borges Garcia Gruber
Home 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

Abstract

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)

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. Quadratic reformulations of nonlinear binary optimization problems. MATHEMATICAL PROGRAMMING, v. 162, n. 1-2, p. 115-144, MAR 2017. Web of Science Citations: 2.
ANTHONY, MARTIN; BOROS, ENDRE; CRAMA, YVES; GRUBER, ARITANAN. Quadratization of symmetric pseudo-Boolean functions. DISCRETE APPLIED MATHEMATICS, v. 203, p. 1-12, APR 20 2016. Web of Science Citations: 5.

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