|
Giovanni Rinaldi is a Research Director of the Italian National Research Council (CNR). He received a master degree in System Science at the Engineering School of the University of Rome in 1976. In 1982 he got a tenured position as a researcher at the Institute on System Analysis and Compute Science (IASI) of the CNR, of which is the director from 2014. He directed the same Institute from 1998 to 2009. He was Visiting Professor at the New York University and at the universities of Augsburg, Cologne and Heidelberg. His main research interests are in Combinatorial Optimization, in particular in the study of structural properties of hard problems and in their exploitation to design efficient exact algorithms. His favorite problems are the Traveling Salesman, the Vehicle Routing and The Max-Cut Problem.
|
Abstract
Quadratic Unconstrained Binary Optimization: some exact and heuristic approaches
Quadratic Unconstrained Binary Optimization (QUBO), i.e., the problem of minimizing a quadratic form in binary variables, is one on the most studied and best known hard discrete optimization problems.
Due to its great interest among the optimizers, several approaches, also of a quite diverse nature, have been proposed to find good or provably good solutions, which makes it also very interesting as a benchmark problem for new algorithmic ideas. Very recently, QUBO has received a renewed attention since a dedicated hardware, based on quantum annealing, has been realized that yields good solution in amazingly short times for some particular instances (the Chimera graphs). In the talk some of the most successful among these approaches are reviewed.
Quadratic Unconstrained Binary Optimization (QUBO), i.e., the problem of minimizing a quadratic form in binary variables, is one on the most studied and best known hard discrete optimization problems.
Due to its great interest among the optimizers, several approaches, also of a quite diverse nature, have been proposed to find good or provably good solutions, which makes it also very interesting as a benchmark problem for new algorithmic ideas. Very recently, QUBO has received a renewed attention since a dedicated hardware, based on quantum annealing, has been realized that yields good solution in amazingly short times for some particular instances (the Chimera graphs). In the talk some of the most successful among these approaches are reviewed.
