Solving linear inequalities systems with local search algorithms

Here, we present a new heuristic on the basis of Balas algorithm for solving systems of linear inequalities with Boolean variables. If a branch in a solution tree leads to a false solution, then a new branch is chosen with the help of simulated annealing technique. The experimental results of fulfilled comparison of new and classical (Balas and simulated annealing) heuristics are listed. Two variants of cost function – sum and maximum – were applied in the new heuristic. The plan of experiments concerned random systems of pseudo-Boolean linear inequalities. According to the results of comparison, the new heuristic is more effective. It was applied to a system of linear inequalities that describes LFSR with a Boolean threshold output function. This system grows exponentially with the length of the output. Some methods for reducing the system size are given. In all cases, the new heuristic allows to find the solution for LFSR sometimes being different from the original.