On effectiveness of solving pseudo-Boolean systems of linear inequalities by simulated annealing, Balas algorithm and interior point algorithm

The aim of this paper is the development and reliability research of the algorithm for solving systems of linear inequalities with Boolean variables, based on variables relaxation, application of the internal point method and the consequent return to Boolean solution. Experimental analysis shows that reliability of the algorithm is about 86 %. This value is higher than the reliability of other heuristic algorithms, applied to the same problem. As the result of experimental research, we have found some classes of systems of inequalities, which are solved by different algorithms with the significantly different reliabilities.