The heuristic algorithms for solving conditional pseudo-Boolean optimization problems have been developed and investigated for special problem classes. These algorithms do not demand explicit assignment of functions. The algorithm of adaptive random search of boundary points that combines random search and greedy heuristic has been created.