Experimental comparison of simulated annealing and balas algorithms for solving linear inequalities | Applied Discrete Mathematics. Supplement. 2014. № 7.

HomeIssuesExperimental comparison of simulated annealing and balas algorithms for solving linear inequalities | Applied Discrete Mathematics. Supplement. 2014. № 7.

Experimental comparison of simulated annealing and balas algorithms for solving linear inequalities

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.

Download file
Counter downloads: 273

Keywords

алгоритм имитации отжига, алгоритм Балаша, линейные неравенства, случайные линейные неравенства, simulated annealing, Balas algorithm, linear inequalities, random linear inequalities

Authors

NameOrganizationE-mail
Anashkina N. V.6237030@mail.ru
Shurupov A. N.ashurupov@mail.ru
Всего: 2

References

Балакин Г. В., Никонов В. Г. Методы сведения булевых уравнений к системам пороговых соотношений // Обозрение прикладной и промышленной математики. 1994. Т. 1. Вып.3. С.389-401.
Анашкина Н. В. Обзор методов решения систем линейных неравенств // Вестник московского университета леса. Лесной вестник. 2004. №1(32). С.144-148.
Кочетов Ю. А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения: Сб. лекций молодежных и научных школ по дискретной математике и ее приложениям. М.: Изд-во центра прикл. исслед. при мех.-мат. фак. МГУ, 2001. С. 84-117.
Goldwasser S. and Bellare M. Lecture Notes on Cryptography. 2001. http://theory.lcs.mit. edu/shafi. 283 p.
Muroga S., Tsuboi T., and Baugh C. R. Enumeration of threshold functions of eight variables // IEEE Trans. Comput. 1970. V. C-19. Iss.9. P. 818-825.
Подольский В. В. Оценки весов персептронов (полиномиальных пороговых булевых функций): автореф. дис.. канд. физ.-мат. наук. М.: МГУ им. М.В. Ломоносова, 2009.
Crama Y. and Hammer P. Boolean Functions. Theory, Algorithms and Applications. Encyclopedia of Mathematics and its Applications / eds. G.-C. Rota. Cambridge University Press, 2011.
Балакин Г. В. Линейные псевдобулевы неравенства // Математические вопросы криптографии. 2010. Т. 1. Вып.3. С. 5-18.
Анашкина Н. В., Шурупов А. Н. Применение алгоритмов локального поиска к решению систем псевдобулевых линейных неравенств // Прикладная дискретная математика. 2014. №3(25) (в печати).
Experimental comparison of simulated annealing and balas algorithms for solving linear inequalities | Applied Discrete Mathematics. Supplement. 2014. № 7.

Experimental comparison of simulated annealing and balas algorithms for solving linear inequalities | Applied Discrete Mathematics. Supplement. 2014. № 7.