Г. О. Маняев, А. Н. Шурупов, “Сравнительный анализ эффективности решения псевдобулевых систем линейных неравенств алгоритмами имитации отжига, Балаша и внутренней точки”, ПДМ. Приложение, 2019, выпуск 12,страницы 218

Вычислительные методы в дискретной математике

Сравнительный анализ эффективности решения псевдобулевых систем линейных неравенств алгоритмами имитации отжига, Балаша и внутренней точки

Г. О. Маняев, А. Н. Шурупов

ФУМО ВО «Информационная безопасность», г. Москва

Аннотация: Целью работы является разработка и исследование надёжности релаксационного алгоритма решения псевдобулевых систем линейных неравенств, построенного на основе алгоритма внутренней точки. Экспериментальный анализ показал высокую (86 %) среднюю надёжность алгоритма, превосходящую аналогичные результаты некоторых эвристических алгоритмов локального поиска при решении случайно выбираемых псевдобулевых систем линейных неравенств. Выявлены классы систем неравенств, на которых сравниваемые эвристические алгоритмы существенно различаются в эффективности решения.

Ключевые слова: псевдобулевы линейные неравенства, алгоритм внутренней точки, релаксация, линейное программирование.

УДК: 512.55

DOI: 10.17223/2226308X/12/61