On effectiveness of solving pseudo-boolean systems of linear inequalities by simulated annealing, balas algorithm and interior point algorithm | Applied Discrete Mathematics. Supplement. 2019. № 12. DOI: 10.17223/2226308X/12/61

On effectiveness of solving pseudo-boolean systems of linear inequalities by simulated annealing, balas algorithm and interior point algorithm

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 the consequent return to Boolean solution. Experimental analysis shows that reliability of the algorithm is about 86%. This value is higher than the reliability of other heuristic algorithms, applied to the same problem. As the result of experimental research, we have found some classes of systems of inequalities, which are solved by different algorithms with the significantly different reliabilities.

Download file

Counter downloads: 117

Keywords

псевдобулевы линейные неравенства, алгоритм внутренней точки, релаксация, линейное программирование, pseudo Boolean linear inequalities, interior point method, relaxation, linear programming

Authors

Name	Organization	E-mail
Manyaev G. O.	FUMO VO "Information Security"	gmolymp@yandex.ru
Shurupov A.N.	FUMO VO "Information Security"	ashurupov@mail.ru

Всего: 2

References

Балакин Г. В., Никонов В. Г. Методы сведения булевых уравнений к системам пороговых соотношений // Обозрение прикл. промышл. матем. Сер. дискрет. матем. 1994. T. 1. №3. С.389-401.

Никонов В. Г. Пороговые представления булевых функций // Обозрение прикл. промышл. матем. Сер. дискрет. матем. 1994. T. 1. №3. С. 402-457.

Черникова Н. В. Алгоритм для нахождения общей формулы неотрицательных решений системы линейных неравенств // Журн. вычисл. матем. и матем. физики. 1965. T. 5. №2. С. 334-337.

Хачиян Л. Г. Избранные труды. М.: МЦНМО, 2009.

Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica. 1984. No. 4. P. 373-395.

Бурделев А. В., Никонов В. Г., Лапиков И. И. Распознавание параметров узла защиты информации, реализованного пороговой k-значной функцией // Труды СПИИРАН. 2016. №46. С. 108-127.

Анашкина Н. В., Шурупов А. Н. Экспериментальное сравнение алгоритмов Балаша и имитации отжига в задаче решения систем линейных неравенств // Прикладная дискретная математика. Приложение. 2014. №7. C. 151-153.

Анашкина Н. В., Шурупов А. Н. Применение алгоритмов локального поиска к решению систем псевдобулевых линейных неравенств // Прикладная дискретная математика. Приложение. 2015. №8. C. 136-138.