О НАДЕЖНОСТИ АЛГОРИТМА РЕШЕНИЯ ПСЕВДОБУЛЕВЫХ СИСТЕМ ЛИНЕЙНЫХ НЕРАВЕНСТВ, ОСНОВАННОГО НА МЕТОДЕ ВНУТРЕННЕЙ ТОЧКИ
(Стр. 48-56)

Подробнее об авторах
Маняев Глеб Олегович сотрудник
ФУМО ВО Информационная безопасность Шурупов Андрей Николаевич сотрудник
ФУМО ВО Информационная безопасность
Чтобы читать текст статьи, пожалуйста, зарегистрируйтесь или войдите в систему
Аннотация:
Для решения непрерывной задачи линейного программирования известен метод внутренней точки (метод Кармаркара [1]). Целью работы является разработка и исследование надежности алгоритма решения псевдобулевых систем линейных неравенств, построенного на основе метода внутренней точки. Идея алгоритма заключается в релаксация исходной задачи, применении метода внутренней точки и возврате к булевому решению. Вместо традиционно используемой целевой функции - невязки системы - в предлагаемом алгоритме выбрана линейная функция от коэффициентов системы. Экспериментальный анализ показал высокую (86%) среднюю надежность алгоритма, превосходящую аналогичные результаты ранее примененных к этой задаче эвристических алгоритмов [2; 3] при решении случайно выбираемых псевдобулевых систем линейных неравенств (77 и 85%, соответственно). В результате экспериментальных исследований выявлены классы систем неравенств, на которых сравниваемые эвристические алгоритмы существенно различаются в эффективности решения. Это позволяет рекомендовать разработанный алгоритм для пополнения класса эвристик, ориентированных на исследуемую задачу. Недостатком разработанного алгоритма является относительно большое время работы.
Образец цитирования:
Маняев Г.О., Шурупов А.Н., (2018), О НАДЕЖНОСТИ АЛГОРИТМА РЕШЕНИЯ ПСЕВДОБУЛЕВЫХ СИСТЕМ ЛИНЕЙНЫХ НЕРАВЕНСТВ, ОСНОВАННОГО НА МЕТОДЕ ВНУТРЕННЕЙ ТОЧКИ. Computational nanotechnology, 4: 48-56.
Список литературы:
Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica. 1984. № 4. Рp. 373-395.
Анашкина Н.В., Шурупов А.Н. Экспериментальное сравнение алгоритмов Балаша и имитации отжига в задаче решения систем линейных неравенств // Прикладная дискретная математика. Приложение. Труды Всероссийской конференции SIBECRYPT’14. № 7. Томский государственный университет, 2014. С. 151-153.
Анашкина Н.В., Шурупов А.Н. Применение алгоритмов локального поиска к решению систем псевдобулевых линейных неравенств. // Прикладная дискретная математика. Приложение. 2015. № 8. С. 136-138.
Балакин Г.В., Никонов В.Г. Методы сведения булевых уравнений к системам пороговых соотношений // Обозрение прикл. промышл. матем. Сер.: «Дискрет, матем.». 1994. Т. 1. № 3. С. 389-401.
Никонов В.Г. Пороговые представления булевых функций // Обозрение прикл. промышл. матем. Сер.: «Дискрет. матем.». 1994. Т. 1. № 3. С. 402-457.
Черникова Н.В. Алгоритм для нахождения общей формулы неотрицательных решений системы линейных неравенств // Ж. вычисл. матем. и матем. физики. 1965. 5. № 2. С. 334-337.
Хачиян Л.Г. Избранные труды. М.: МЦНМО, 2009.
Бурделев А.В., Никонов В.Г., Лапиков И.И. Распознавание параметров узла защиты информации, реализованного пороговой k-значной функцией // Труды СПИИРАН. 2016. Вып. 46. C. 108-127.