Joint BCAM-UPV/EHU Data Science and Artificial Intelligence seminar: Advances in Rankings Generated by Pseudo-Boolean Functions

Link to the session here

Abstract
In the field of combinatorial optimization, it is known that any algorithm performs on average as well as a random search over all optimization problem instances. Due to that, the idilic goal in this area is to present an association function that, given a problem instance, it returns the most efficient algorithm to solve it. Bearing this objective in mind, this presentation focuses on the study of the search space of pseudo-Boolean functions to obtain new knowledge about binary-based Combinatorial Optimization Problems. First, we compute the Walsh transform and the Walsh decomposition over several binary-based Combinatorial Optimization Problems. Secondly, we present new insights between the relation of the degree of a pseudo-Boolean function and the rankings of solutions that can be generated. Finally, we run several experiments of the possible rankings generated by the Unconstrained Binary Quadratic Problem and the Number Partitioning Problem.