Pseudo-Boolean Optimization

Yves Crama and Peter L. Hammer

ABSTRACT

This article briefly surveys some fundamental results concerning pseudo-Boolean functions, that is, real-valued functions of 0-1 variables. Hundreds of papers have been devoted to the investigation of pseudo-Boolean functions, and a rich and diversified theory has now emerged from this literature. The article states local optimality conditions, outlines basic techniques for global pseudo-Boolean optimization, and shows connections between best linear approximations of pseudo-Boolean functions and game theory. It also describes models and applications arising in various fields, ranging from combinatorics to management science, and points to several classes of functions of special interest.