Geodesic
Experimental comparison of Simulated Annealing and Balas Algorithms for Solving Linear Inequalities
Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 151-153.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{PDMA_2014_7_a64,
     author = {N. V. Anashkina and A. N. Shurupov},
     title = {Experimental comparison of {Simulated} {Annealing} and {Balas} {Algorithms} for {Solving} {Linear} {Inequalities}},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {151--153},
     publisher = {mathdoc},
     number = {7},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2014_7_a64/}
}
TY  - JOUR
AU  - N. V. Anashkina
AU  - A. N. Shurupov
TI  - Experimental comparison of Simulated Annealing and Balas Algorithms for Solving Linear Inequalities
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2014
SP  - 151
EP  - 153
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2014_7_a64/
LA  - ru
ID  - PDMA_2014_7_a64
ER  - 
%0 Journal Article
%A N. V. Anashkina
%A A. N. Shurupov
%T Experimental comparison of Simulated Annealing and Balas Algorithms for Solving Linear Inequalities
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2014
%P 151-153
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2014_7_a64/
%G ru
%F PDMA_2014_7_a64
N. V. Anashkina; A. N. Shurupov. Experimental comparison of Simulated Annealing and Balas Algorithms for Solving Linear Inequalities. Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 151-153. http://geodesic.mathdoc.fr/item/PDMA_2014_7_a64/

[1] Balakin G. V., Nikonov V. G., “Metody svedeniya bulevykh uravnenii k sistemam porogovykh sootnoshenii”, Obozrenie prikladnoi i promyshlennoi matematiki, 1:3 (1994), 389–401 | Zbl

[2] Anashkina N. V., “Obzor metodov resheniya sistem lineinykh neravenstv”, Vestnik moskovskogo universiteta lesa. Lesnoi vestnik, 2004, no. 1(32), 144–148

[3] Kochetov Yu. A., “Veroyatnostnye metody lokalnogo poiska dlya zadach diskretnoi optimizatsii”, Diskretnaya matematika i ee prilozheniya, Sb. lektsii molodezhnykh i nauchnykh shkol po diskretnoi matematike i ee prilozheniyam, Izd-vo tsentra prikl. issled. pri mekh.-mat. fak. MGU, M., 2001, 84–117

[4] Goldwasser S., Bellare M., Lecture Notes on Cryptography, 2001, 283 pp. http://people.csail.mit.edu/joanne/shafi-pubs.html

[5] Muroga S., Tsuboi T., Baugh C. R., “Enumeration of threshold functions of eight variables”, IEEE Trans. Comput., C-19:9 (1970), 818–825 | DOI

[6] Podolskii V. V., Otsenki vesov perseptronov (polinomialnykh porogovykh bulevykh funktsii), Avtoref. dis. $\dots$ kand. fiz.-mat. nauk, MGU im. M. V. Lomonosova, M., 2009

[7] Crama Y., Hammer P., Boolean Functions. Theory, Algorithms and Applications, Encyclopedia of Mathematics and its Applications, eds. G.-C. Rota, Cambridge University Press, 2011 | MR | Zbl

[8] Balakin G. V., “Lineinye psevdobulevy neravenstva”, Matematicheskie voprosy kriptografii, 1:3 (2010), 5–18

[9] Anashkina N. V., Shurupov A. N., “Primenenie algoritmov lokalnogo poiska k resheniyu sistem psevdobulevykh lineinykh neravenstv”, Prikladnaya diskretnaya matematika, 2014, no. 3(25) (to appear)