Old and new algorithms for polynomial unconstrained optimization problems in binary variables

Polynomial unconstrained optimization problems in binary variables (PUBO) are notoriously hard to solve. This talk presents an overview of recent advances which are revisiting ideas introduced more than 50 years ago. A first idea consists in solving the PUBO problem by dynamic programming techniques which eliminate variables one by one, iteratively, until the problem becomes trivial. This approach, initially proposed in the 1960s, is rather inefficient in general but can be shown to work extremely well, both in theory and in practice, when appropriately implemented on special classes of instances. The second idea, introduced around 1975, allows the transformation of any instance of PUBO into an equivalent quadratic binary optimization problem. Several efficient transformations have been recently proposed for this purpose and different algorithms can be used to solve the resulting quadratic problem. The talk will present a brief overview of this literature and of comparative computational experiments.