ON CLASES OF FUNCTIONS WITH BINARY VARIABLES

The scheme proposed below is often used for solving problems and developing optimization algorithms. To solve a specific problem an efficient algorithm of optimization has been developed. The proposed algorithm combines several classes of problems by generelasing and determining a function class. For this reason establishing correlation among available classes of functions with binary variables in different experiments allows to apply even not perfect optimization algorithms.
In this paper we consider a question on correlation of the function classes based on the different approaches to classification itself. First approach offers classes of separable, modular and submodular function; second one offers function classes based on structural features of the set of binary variables: monotone, unmonotone and w eakly unmonotone functions. It has been proven that separable functions are always unimodal and monotone ones. The results obtained in this study will allow to use a more efficient algorithm for optimization of separable and modular functions.

pseudoboolean functions, optimization