This article is cited in 3 papers

Computational methods in discrete mathematics

Experimental comparison of Simulated Annealing and Balas Algorithms for Solving Linear Inequalities

N. V. Anashkina^a, A. N. Shurupov<sup>b

a</sup> Moscow
^b Moscow State Institute of Radio-Engineering, Electronics and Automation, Moscow

Abstract: An experimental comparison of well-known heuristics – simulated annealing (SA) and Balas (BA) algorithms – are presented for solving random systems of linear inequalities (LIS) with Boolean variables. Randomness is treated in a traditional matter. Both algorithms were applied to each LIS. Experiments were divided into 10 series with 800 systems per each series. Only simultaneous inequalities were generated. The conclusion derived from results of experiments is that probabilistic local search algorithms are more effective and time consuming in comparison with deterministic algorithms. Recommendations to joint using of BA and SA are provided. A new interpretation of random linear inequality is offered. It can be used for more exact comparison of solving algorithms for inequalities systems deduced from systems of Boolean equations.

Keywords: simulated annealing, Balas algorithm, linear inequalities, random linear inequalities.

UDC: 512.55