Boolean optimization algorithm on (0,1)-matrices (Q1802588)

Proposed is a heuristic algorithm for the solution of some class of NP- complete problems with Boolean variables. The solution of problems of this class can be presented as search of a maximal zero submatrix in a given symmetric (0,1)-matrix with zero main diagonal. The general idea of this algorithm is connected with stepping in the best direction, the last being determined as mathematical expectation of a number of maximal zero submatrices. In some cases this approach is 10 times faster than the famous regular algorithms, such as branch and bound methods.