On a success rate of internal point algorithm for solving systems of linear inequalities with boolean variables

The interior point method (Karmarkar’s method [1]) is well known for its solution of the continuous problem of linear programming. 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 following return to Boolean solution. In our algorithm a system’s coefficients linear function was chosen instead of the system discrepancy, which is traditionally used as an objective function. Experimental analysis showed that reliability of the algorithm is about 86%. This value is higher than the reliability (77 & 85%) of other heuristic algorithms, applied to the same problem [2; 3]. As the result of experimental research, we found some classes of systems of inequalities, which are solved by different algorithms with significantly different reliabilities. These results allow of recommending the developed algorithm for addition to the class of heuristics, oriented on the researched problem. The drawback of the developed algorithm is relatively long working time.