О НАДЕЖНОСТИ АЛГОРИТМА РЕШЕНИЯ ПСЕВДОБУЛЕВЫХ СИСТЕМ ЛИНЕЙНЫХ НЕРАВЕНСТВ, ОСНОВАННОГО НА МЕТОДЕ ВНУТРЕННЕЙ ТОЧКИ
(Стр. 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.
Анашкина Н.В., Шурупов А.Н. Экспериментальное сравнение алгоритмов Балаша и имитации отжига в задаче решения систем линейных неравенств // Прикладная дискретная математика. Приложение. Труды Всероссийской конференции 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.
