On Validating Boolean Optimizers

Boolean optimization finds a wide range of application domains, that motivated different organizations of Boolean optimizers. Some of the most successful approaches are based on iterative calls to an NP oracle. The increasing use of Boolean optimizers in practical settings raises the question of confidence in computed results. Recent work studied the validation of Boolean optimizers based on branch-and-bound search. This paper complements existing work, and develops methods for validating Boolean optimizers based on iterative calls to an NP oracle. Preliminary results indicate that the impact of the proposed method in overall performance is negligible.